【BZOJ3884】上帝与集合的正确用法 [欧拉定理]

上帝与集合的正确用法

Time Limit: 5 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

Input

　　第一行一个T，接下来T行，每行一个正整数p，代表你需要取模的值。

Output

　　T行，每行一个正整数，为答案对p取模后的值。

Sample Input

　　3
　　2
　　3
　　6

Sample Output

　　0
　　1
　　4

HINT

　　对于100%的数据，T<=1000，p<=10^7

Solution

　　我们运用欧拉定理：

　　然后还有一个定理：一个数在执行log次操作后，值不会改变。

　　然后就可以直接求了。

Code

 1 #include<iostream>    
 2 #include<string>    
 3 #include<algorithm>    
 4 #include<cstdio>    
 5 #include<cstring>    
 6 #include<cstdlib>
 7 #include<cmath>
 8 using namespace std;  
 9 typedef long long s64;
10 
11 const int ONE = 500005;
12 const int INF = 2147483640;
13 
14 int T,x;
15 int phi[ONE],pn;
16 
17 int get()
18 {    
19         int res=1,Q=1;char c;    
20         while( (c=getchar())<48 || c>57 ) 
21         if(c=='-')Q=-1; 
22         res=c-48;     
23         while( (c=getchar())>=48 && c<=57 )    
24         res=res*10+c-48;    
25         return res*Q;
26 }
27 
28 int Quickpow(int a,int b,int MOD)
29 {
30         int res = 1;
31         while(b)
32         {
33             if(b & 1) res = (s64)res * a % MOD;
34             a = (s64)a * a % MOD;
35             b >>= 1; 
36         }
37         return res;
38 }
39 
40 int Getphi(int n)
41 {
42         int res = n;
43         for(int i=2; i*i<=n; i++)
44         if(n % i == 0)
45         {
46             res = res/i*(i-1);
47             while(n % i == 0) n /= i;
48         }
49         if(n != 1) res = res/n*(n-1);
50         return res;
51 }
52 
53 int Deal(int p)
54 {
55         pn = 0;    phi[0] = p;
56         while(p != 1) phi[++pn] = p = Getphi(p);
57         phi[++pn] = 1;
58         
59         int a = 2;
60         for(int i=pn; i>=1; i--)
61         {
62             if(a >= phi[i]) a = a%phi[i] + phi[i];
63             a = (s64)Quickpow(2, a, phi[i-1]);
64             if(!a) a = phi[i-1];
65         }
66         
67         return a % phi[0];
68 }
69 
70 int main()
71 {
72         T = get();
73         while(T--)
74         {
75             x = get();
76             printf("%d
", Deal(x));
77         }
78 }

View Code