题目链接：

题目大意：

he[n]为小于n且满足x^2 = x (mod n)的个数

hehe[n] = He[1]*……*He[N]

解题思路：

1.证明p是素数时He[p]=2.     

 x^2=x(mod p)—->p|x(x-1).因为x<p所以p不整除x也不整除x-1.所以成立的情况下是x=1或者x=0.

He[p^k]=2,证明类似上面的

 

2.证明对于不同的两个素数p和q,He[p*q]=4=He[p]*He[q];

首先x=0和x=1是肯定成立的,

现在由x^2=x(mod p*q)

       —>p*q|x(x-1)

     假设x=k*p[k<q]

     ——>p*q|k*p(k*p-1)

    ——->q|k(k*p-1)

   ——->q|(k*p-1)  因为k<q  q是素数 所以gcd(k,q)=1

  ——->k*p+t*q=1

 这里就变成了这个方程的解,由扩展欧几里得知,这个方程有解,但是k在[0,q-1]之内的解就一个,所以这里多一个解,同理设x=k*p又有一个解,所以x^2=x(mod p*q)有4个解(x=0 ,x=1 ,x=k*p, x=k*q)

—->He[p*q]=4=He[p]*He[q];

那么He[p1^r1*p2^r2*……*pk^rk]=2^k然后可以进一步算出HeHe只需要算n以内每个素数的倍数的个数.

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int maxn = 10000000+10; 5 int prime[maxn]; 6 bool is_prime[maxn]; 7 int sieve(int n)//返回n以内素数的个数 8 { 9     int p = 0;10     for(int i = 0; i <= n; i++)is_prime[i] = 1;11     is_prime[0] = is_prime[1] = 0;12     for(ll i = 2; i <= n; i++)13     {14         if(is_prime[i])15         {16             prime[p++] = i;17             for(ll j = i * i; j <= n; j += i)is_prime[j] = 0;//这里涉及i*i,必须使用long long18         }19     }20     return p;21 }22 ll pow(ll a, ll b, ll m)23 {24     ll ans = 1;25     a %= m;26     while(b)27     {28         if(b & 1)ans = (ans % m) * (a % m) % m;29         b /= 2;30         a = (a % m) * (a % m) % m;31     }32     ans %= m;33     return ans;34 }35 int main()36 {37     int T;38     cin >> T;39     int tot = sieve(10000000), n, m;40     while(T--)41     {42         cin >> n >> m;43         int cnt = 0;44         for(int i = 0; i < tot && prime[i] <= n; i++)45         {46             cnt += n / prime[i];47         }48         cout<