本身是个找规律的题目,不过找到后,给队友不慎写错了,后来我重写,就过掉了。规律是,如果不是完全平方数的话,奇数一定是,偶数一定不是。如果是完全平方数的话,反之。 赛后问了moreD,得到这个证明: 如果a是一个不和x互质也不能整除x的数,那么我们可以把它写成两部分a=a’k,k=gcd(a,x)。 k是x的一个约数。 a’不能被x/k整除。 若:gcd(a’,x/k)=1 eular(x/k)-1就是a’能够有的情况数,因为a’!=1,所以减去1。 若:gcd(a’,x/k)=g!=1,那么把g乘到k,我们能够得到: gk是x的一个约数 a’/g不能被x/k/g整除。 eular(x/k/g)-1就是a’/g的所有情况。 所以题目的函数f(x)={对于所有x的约数k求和[eular(x/k)-1]}={对于所有x的约数k求和[eular(k)-1]}={对于所有x的约数k求和[eular(k)]}-[x的约数的个数]。 如果x是个完全平方数,那么x约数的个数一定是个奇数个(约数都是两对应的例如10=2*5,2和5对应),所以后面减去奇数个1,反之,减去偶数个1。 如果x是个奇数,那么不含2的约数,eular(k)就全是偶数,和也跟着是偶数;反之,和就是奇数。(欧拉函数除了euler(2),都是偶数)。 综上,如果x是完全平方数,又是偶数的话….讨论一下就是今天那个规律了。