Cows and Primitive Roots

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

The cows have just learned what a primitive root is! Given a prime p, a primitive root is an integer x (1?≤?x?<?p) such that none of integers x?-?1,?x²?-?1,?...,?x^p?-?2?-?1 are divisible by p, but x^p?-?1?-?1 is.

Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime p, help the cows find the number of primitive roots .

Input

The input contains a single line containing an integer p (2?≤?p?<?2000). It is guaranteed that p is a prime.

Output

Output on a single line the number of primitive roots .

Sample test(s) Input 3 Output 1 Input 5 Output 2 Note

The only primitive root is 2.

The primitive roots are 2 and 3.

可使用蠻力法，但需要注意兩點：

1、不要每次都用pow計算x的n次方，由于x^n=x*X^(n-1)，設一個變量m儲存x^(n-1)，那么x^n=m*x.

2、如果直接算出m，就算用64位也會溢出，利用性質（a-b）%p=(a%p-b%p)%p，則只需保留m%p的值。

AC Code：

1 #include <iostream> 2 #include <fstream> 3 #include <string> 4 #include <set> 5 #include <map> 6 #include <vector> 7 #include <stack> 8 #include <queue> 9 #include <cmath> 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 #include <utility> 14 using namespace std; 15 #define ll long long 16 #define cti const int 17 #define ctll const long long 18 #define dg(i) cout << '*' << i << endl; 19 20 int main() 21 { 22 ll p, x; 23 ll m; 24 int ans; 25 bool ok; 26 while(scanf("%I64d", &p) != EOF) 27 { 28 ans = 0; 29 for(x = 1; x < p; x++) 30 { 31 m = 1; 32 ok = true; 33 for(int i = 1; i < p - 1; i++) 34 { 35 m *= x; 36 m %= p; 37 if((m - 1) % p == 0) 38 { 39 ok = false; 40 break; 41 } 42 } 43 if(ok && ((m * x) - 1) % p == 0) ans++; 44 } 45 printf("%d\n", ans); 46 } 47 return 0; 48 }

?

轉載于:https://www.cnblogs.com/cszlg/archive/2013/03/22/2975423.html

總結

以上是生活随笔為你收集整理的Codeforces Round #174 (Div. 2) Cows and Primitive Roots（数论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。