TOJ 2793.A Simple Problem

题目链接：http://acm.tju.edu.cn/toj/showp2793.html

2793.    A Simple Problem

---

Time Limit: 1.0 Seconds    Memory Limit: 65536K Total Runs: 554    Accepted Runs: 266

---

Given a nonnegative integer  a, and a positive integer  N, we define:

f(a, 1) = a  f(a, k) = f(a, k - 1) * f(a, k - 1) % N, k > 1

There may or may not exist some positive integer k satisfying f(a, k) = 0.

Your task is, given a positive integer N, to determine how many a (0 ≤ a ≤ N) there are, such that for some positive integer k, f(a, k) = 0.

Input

The input contains an integer  T on the first line, indicating the number of test cases. Each test case contains only one positive integer  N (1 ≤  N ≤ 1000000000) on a line.

Output

For each test case, output the answer on a single line.

Sample Input

6 2 12 50 180 245 361

Sample Output

2 3 6 7 8 20 Source: The 5th UESTC Programming Contest

---

Submit   List    Runs   Forum   Statistics

数论题目，好好分析就可得出，要使f(a, k)=0，则a必须是N的所有素因数乘积的倍数，知道这一点后只需要求出素因数乘积p即可。

#include <stdio.h> using namespace std; bool isPrime(int n){ for(int i=2;i*i<=n;i++){ if(n%i==0) return false; } return true; } int main(){ int t,n,p; scanf("%d",&t); while(t--){ scanf("%d",&n); int tag=n; p=1; if(n==1) p=1; else if(isPrime(n)) p=n; else{ for(int i=2;i<=n;i++) if(n%i==0 && isPrime[i]){ p*=i; while(n%i==0) n/=i; } } printf("%d\n",tag/p+1); } }