1.2.关于gcd(),记作(),支持几种操作:(n-x,n)=(-x,n)=(x,n)也就是说,一边加到另一边,一边取反,gcd的还是不变的.可以由同余的性质证明.
 2.1.每次符合条件k的指数就会增加,所以问题就变成了1-n里面和n互质的数,的和.
 2.2.欧拉定理,即费马小定理的推广,介绍了欧拉函数phi(x)表示小于x的数里面,与x互质的数,的个数.有1.1得到的结论,如果x和n互质,那么n-x也和n互质.两数之和等于n.所以两两配个对.所有数之和 sum(x)=n \times φ(n) \div 2
 2.3.关于n或phi(n)的奇偶,如果phi(n)是奇数,那么n/2就会和n互质.但由于n/2还是n的一个约数.所以n只能为2.所以phi(n)为奇数当且仅当n=2,此时也可以整除.同时证明了当n不等于2的时候phi(n)一定为偶数.
 3.1.最后快速幂处理答案.注意模
 using namespace std;
 typedef long long ll;
 ll res=1;
 return res %mod;
 ll euler=n,bn=n;