记录编号	360379	评测结果	AAAAAAAAAA
题目名称	2136.[SGU U294]他的圆圈	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.528 s
提交时间	2016-12-29 15:52:35	内存使用	2.60 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <cstring>
#include <string>
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

#define MAXN 200021
int phi[MAXN], primes[MAXN], tot;
bool vis[MAXN];
void calc_phi(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            phi[i] = i-1;
            primes[tot++] = i;
        }    
        for(int j = 0; j < tot; j++)
        {
            int k = i*primes[j];
            if(k > n)break;
            vis[k] = true;
            if(i%primes[j])
            {
                phi[k] = phi[i]*(primes[j]-1);
            }else 
            {
                phi[k] = phi[i]*primes[j];break;
            }
        }
    }
}

int POW[4]={1,10,100,1000};
const int mod=10000;
struct ExtInt{
    int num[20010],len;
    ExtInt(int x){len=0;
        memset(num,0,sizeof(num));
        do{
            num[++len]=x%mod;
            x/=mod;
        }while(x);
    }
    
    void Scf(){
        char s[10010];scanf("%s",s+1);
        memset(num,0,sizeof(num));len=1;
        for(int i=strlen(s+1),cnt=0;i>=1;i--){
            num[len]+=POW[cnt++]*(s[i]-'0');
            if(cnt==4)cnt=0,len+=1;
        }
    }
    
    int operator [](int x){
        return num[x];
    }    
    
    void Prf(){
        printf("%d",num[len]);
        for(int i=len-1;i>=1;i--)
            printf("%04d",num[i]);
        printf("\n");    
    }
};

ExtInt operator +(ExtInt a,int b){
    ExtInt ret(0);
    ret.len=a.len;
    for(int i=1,in=0;i<=ret.len||in;i++){
        ret.num[i]=a[i]+b+in;in=ret[i]/mod;
        ret.num[i]%=mod;ret.len=max(ret.len,i);
    }
    return ret;
}

ExtInt operator +(ExtInt a,ExtInt b){
    ExtInt ret(0);
    ret.len=max(a.len,b.len);
    for(int i=1,in=0;i<=ret.len||in;i++){
        ret.num[i]=a[i]+b[i]+in;in=ret[i]/mod;
        ret.num[i]%=mod;ret.len=max(ret.len,i);
    }
    return ret;
}

ExtInt operator *(ExtInt a,ExtInt b){
    ExtInt ret(0);
    for(int i=1;i<=a.len;i++){
        for(int j=1,in=0;j<=b.len||in;j++){    
            ret.num[i+j-1]+=a[i]*b[j]+in;in=ret[i+j-1]/mod;
            ret.num[i+j-1]%=mod;ret.len=max(ret.len,i+j-1);
        }
        while(!ret[ret.len])
            ret.num[ret.len--]=0;
        ret.len=max(ret.len,1);    
    }
    return ret;
}

ExtInt operator ^(ExtInt a,int k){
    ExtInt ret(1);
    while(k){
        if(k&1)ret=ret*a;
        k>>=1;a=a*a;    
    }
    return ret;
}

ExtInt operator /(ExtInt a,int k){
    for(int i=a.len,tot=0;i>=1;i--){
        tot=tot*10000+a[i];
        a.num[i]=tot/k;
        tot%=k;
    }
    while(!a[a.len])
        a.num[a.len--]=0;
    return a;
}

int main()
{
    freopen("Hescircle.in", "r", stdin);
    freopen("Hescircle.out", "w", stdout);
    int n;scanf("%d", &n);
    calc_phi(n);
    ExtInt ans(0);
    for(int i = 1; i <= n; i++)
    {
        if(n%i == 0)
        {
            ExtInt x(2);
            ans = ans+(x^i)*phi[n/i];
        }
    }
    ans = ans/n;
    ans.Prf();
    return 0;
}