记录编号	402936	评测结果	AAAAAAAAAA
题目名称	[SGU U294]他的圆圈	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2017-05-08 14:25:02	内存使用	34.02 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstdarg>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int gcd(int a, int b){return b?gcd(b, a%b):a;}
typedef vector<unsigned long long> metacont;
struct virt{
  double a, b;
  void operator=(int p){a = p, b = 0.0;}
  virt(double x = 0, double y = 0){a = x, b = y;}
  virt operator+(virt &r){return virt(a+r.a, b+r.b);}
  virt operator-(virt &r){return virt(a-r.a, b-r.b);}
  virt operator*(double p){return virt(a*p, b*p);}
  virt operator*(virt &r){return virt(a*r.a-b*r.b, a*r.b+b*r.a);}
};
virt pa[(1<<20)+1];
virt pb[(1<<20)+1];
const double PI = acos(-1);
void rader(virt *a, int n){
  int j = n>>1;
  for(int i = 1; i < n-1; i++){
    if(i < j)swap(a[i], a[j]);
    int k = n>>1;
    while(j >= k){
      j -= k; k >>= 1;
    }if(j < k)j += k;
  }
}
void fft(virt *a, int n, bool idft = false){
  rader(a, n);
  double pi = idft?PI:-PI;
  for(int h = 2; h <= n; h <<= 1){
    virt omgn(cos(2*pi/h), sin(2*pi/h));
    for(int j = 0; j < n; j += h){
      virt omg(1, 0);
      for(int k = j; k < j+h/2; k++){
        virt u = a[k], v = omg*a[k+h/2];
        a[k] = u+v, a[k+h/2] = u-v;
        omg = omg*omgn;
      }
    }
  }
  if(idft)for(int i = 0; i < n; i++)a[i].a /= n;
}
void mul(metacont &a, metacont &b){
  int la = 0, lb = 0;
  int s = 0;
  for(metacont::iterator it = a.begin(); it != a.end(); ++it)
    pa[la++] = *it;
  for(metacont::iterator it = b.begin(); it != b.end(); ++it)
    pb[lb++] = *it;
  while((1<<s) <= la+lb)s++; s = 1<<s;
  for(int i = la; i < s; i++)pa[i] = 0;
  for(int i = lb; i < s; i++)pb[i] = 0;
  fft(pa, s); fft(pb, s);
  for(int i = 0; i < s; i++)pa[i] = pa[i]*pb[i];
  fft(pa, s, true);
  a.resize(la+lb-1);
  for(int i = 0; i <= la+lb-2; i++)
    a[i] = (unsigned long long)(pa[i].a+0.5);
}
static const int BASE = 1000;
static const int BMAX = 3;
static const int BPOW[] = {1, 10, 100};
struct bignum{
  metacont bits;
  inline void init(int v){
    bits.push_back(v);
  }
  inline int length(){return bits.size();}
  void addw(bignum &o){ 
    int s = 0;
    if(length() > o.length()){
      s = length(); o.bits.resize(s);
    }else{
      s = o.length(); bits.resize(s);
    }
    for(int i = 0; i < s; i++){
      bits[i] += o.bits[i];
    }
    if(bits[s-1] > BASE)bits.push_back(0);
    for(int i = 0; i+1 < length(); i++){
      bits[i+1] += bits[i]/BASE;
      bits[i] %= BASE;
    }
  }
  void carray(){
    for(int i = 0; i < length(); i++){
      if(bits[i] >= BASE)
      if(i+1 == length())bits.push_back(bits[i]/BASE);     
      else bits[i+1] += bits[i]/BASE;
      bits[i] %= BASE;
    }
  }
  inline bool is_zero(){return bits[length()-1] == 0;}
  void mulw(bignum &o){
    if(is_zero())return;
    if(o.is_zero()){bits.clear(); init(0); return;}
    mul(bits, o.bits); 
    carray();
  }
  void mulw(int x){
    if(is_zero())return;
    if(!x){
      bits.clear(); init(0); return;
    }
    for(int i = 0; i < length(); i++)bits[i] *= x;
    carray(); 
  }
  void divw(int k){
    unsigned long long t = 0;
    for(int i = bits.size()-1; ~i; i--){
      t = t*BASE+bits[i];
      bits[i] = t/k;
      t %= k;
    }
    if(length() == 1)return;
    while(!bits[length()-1])bits.pop_back();
  }
  void print( ){
    printf("%llu", bits[length()-1]);
    for(int i = bits.size()-2; ~i; i--)printf("%03llu", bits[i]); putchar('\n');
  }
  void get(){
    static char buf[152];
    scanf("%s", buf);
    int cnt = 0;
    int cur = 0;
    for(int i = strlen(buf)-1, x; ~i; i--){
      if(length() <= cur)bits.push_back(BPOW[cnt++]*(buf[i]-'0'));
      else bits[cur] += BPOW[cnt++]*(buf[i]-'0');
      if(cnt == BMAX)cnt = 0, cur++;
    }
  }
};
void fast_pow(bignum &a, int x){
  bignum b = a;
  a.bits.clear(); a.init(1);
  while(x){
    if(x&1)a.mulw(b);
    x >>= 1;
    b.mulw(b);
  }
}
const int MAXN = 200001;
int phi[MAXN], pm[MAXN], tot; bool vis[MAXN];
void pre(int n){
  phi[1] = 1;
  for(int i = 2; i <= n; i++){
    if(!vis[i]){
      pm[tot++] = i;
      phi[i] = i-1;
    }
    for(int j = 0; j < tot; j++){
      int k = pm[j]*i; if(k > n)break; vis[k] = true;
      if(i%pm[j])phi[k] = phi[i]*(pm[j]-1);
      else{
        phi[k] = phi[i]*pm[j]; break;
      }        
    }
  }
}
int main(){
  freopen("Hescircle.in", "r", stdin);
  freopen("Hescircle.out", "w", stdout);
  int n; scanf("%d", &n);
  pre(n);
  bignum sum; sum.init(0);
  for(int i = 1; i <= n; i++){
    if(n%i == 0){
      bignum t; t.init(2);
      fast_pow(t, i);
      t.mulw(phi[n/i]);
      sum.addw(t);
    }
  }
  sum.divw(n);
  sum.print();
  return 0;
}