题目大意： 组成，求有多少本质不同的环。
分析： 的置换会出现次，所以答案就是：
高精度压压位，，优化一下常数就过了。
AC code：
LL;typedef double DB;LD;;void open_init(){#ifndef ONLINE_JUDGEfreopen(“input.txt”, “r”, stdin);freopen(“output.txt”, “w”, stdout);#endifios::sync_with_stdio(0);}void close_file(){#ifndef ONLINE_JUDGEfclose(stdin);fclose(stdout);#endif}const int MAXN = 200009;const int MAX = 10009;const int M = 1e8;struct Bignum{LL a[MAX];Bignum(){clr(a, 0);a[0] = 1;}Bignum(int k){clr(a, 0);a[0] = 1;if(k){a[0] = 0;while(k){a[++a[0]] = k%M;k /= M;}}}Bignum& operator = (const Bignum &b){clr(a, 0);memcpy(a, b.a, (b.a[0]+1)*sizeof(LL));return *this;}inline void read(){char str[MAX] = “\0”;scanf(“%s”, str);a[0] = strlen(str);per(i, a[0], 1)a[a[0]-i+1] = str[i-1]-‘0’;}inline void adjust(){LL tmp;rep(i, 1, a[0]){if(a[i] >= M){tmp = a[i]/M;a[i+1] += tmp, a[i] -= tmp*M;}if(a[i] < 0){tmp = (a[i]+1)/M+1;a[i+1] -= tmp, a[i] += tmp*M;}}while(a[a[0]+1]) a[0]++;while(a[0] > 1 && !a[a[0]]) a[0]–;}inline void write(){printf(“%d”, (int)a[a[0]]);per(i, a[0]-1, 1)printf(“%08d”, (int)a[i]);}};< (const Bignum &a, const Bignum &b){if(a.a[0] != b.a[0]) return a.a[0] < b.a[0];per(i, a.a[0], 1)if(a.a[i] != b.a[i])return a.a[i] < b.a[i];return false;}== (const Bignum &a, const Bignum &b){if(a.a[0] != b.a[0]) return false;rep(i, 1, a.a[0])if(a.a[i] != b.a[i])return false;return true;} > (const Bignum &a, const Bignum &b){if(a.a[0] != b.a[0]) return a.a[0] > b.a[0];per(i, a.a[0], 1)if(a.a[i] != b.a[i])return a.a[i] > b.a[i];return false;}<= (const Bignum &a, const Bignum &b){return !(a > b);}>= (const Bignum &a, const Bignum &b){return !(a < b);}inline Bignum operator + (const Bignum &a, const Bignum &b){Bignum ret;int len = max(a.a[0], b.a[0]);rep(i, 1, len)ret.a[i] = a.a[i]+b.a[i];ret.a[0] = len;ret.adjust();return ret;}+= (Bignum &a, const Bignum &b){a = a+b;}inline Bignum operator – (const Bignum &a, const Bignum &b){Bignum ret;int len = a.a[0];rep(i, 1, len)ret.a[i] = a.a[i]-b.a[i];ret.a[0] = len;ret.adjust();return ret;}-= (Bignum &a, const Bignum &b){a = a-b;}inline Bignum operator * (const Bignum &a, int k){Bignum ret;ret.a[0] = a.a[0];rep(i, 1, a.a[0])ret.a[i] = a.a[i]*k;ret.adjust();return ret;}inline Bignum operator * (const Bignum &a, const Bignum &b){Bignum ret;ret.a[0] = a.a[0]+b.a[0]-1;rep(i, 1, a.a[0])rep(j, 1, b.a[0])ret.a[i+j-1] += a.a[i]*b.a[j];ret.adjust();return ret;}template<class T>*= (Bignum &a, const T &b){a = a*b;}inline Bignum operator / (const Bignum &a, const Bignum &b){Bignum ret, tmp;ret.a[0] = a.a[0];per(i, a.a[0], 1){tmp = tmp*M+a.a[i];int l = 0, r = M-1;while(l < r){int mid = (l+r+1)>>1;if(b*mid > tmp) r = mid-1;else l = mid;}tmp -= b*l;ret.a[i] = l;}ret.adjust();return ret;}/= (Bignum &a, const Bignum &b){a = a/b;}inline Bignum operator % (const Bignum &a, const Bignum &b){return a-a/b*b;}%= (Bignum &a, const Bignum &b){a = a%b;}int n;int phi[MAXN];int prime[MAXN], tot;bool is[MAXN];vector<int> fac;Bignum ans;inline void euler(int n){phi[1] = 1;rep(i, 2, n){if(!is[i]){prime[++tot] = i;phi[i] = i-1;}for(int j = 1; j <= tot && (LL)prime[j]*i <= n; ++j){is[i*prime[j]] = true;if(i%prime[j] == 0){phi[i*prime[j]] = phi[i]*prime[j];break;}else phi[i*prime[j]] = phi[i]*phi[prime[j]];}}}inline void fac_decomp(int n){rep(i, 1, n)if(i*i > n) break;else if(n%i == 0){fac.pb(i);if(i*i != n)fac.pb(n/i);}}template<class T> T power(T a, int b){T base(a), ret(1);while(b){if(b&1) ret *= base;base *= base;b >>= 1;}return ret;}int main(){open_init();cin >> n;euler(n);fac_decomp(n);rep(i, 0, fac.size()-1){int d = fac[i], t = phi[n/d];ans += power(Bignum(2), d)*t;}ans /= n;ans.write();close_file();return 0;}
梦想让我与众不同，奋斗让我改变命运！
