ural 1204. Idempotents

1204. Idempotents

Time limit: 1.0 second
Memory limit: 64 MB

The number x is called an idempotent modulo n if

x*x = x (mod n)

Write the program to find all idempotents modulo n, where n is a product of two distinct primes p and q.

Input

First line contains the number k of test cases to consider (1 ≤ k ≤ 1000). Each of the following k lines contains one number n < 10⁹.

Output

Write on the i-th line all idempotents of i-th test case in increasing order. Only nonnegative solutions bounded by n should be printed.

Sample

input	output
3 6 15 910186311	0 1 3 4 0 1 6 10 0 1 303395437 606790875

Problem Author: Pavel Atnashev
Problem Source: USU Internal Contest, March 2002

大意：给出n, 求x, 使得x*x = x(mod n)

思路：x1 = 0, x2 = 1时公式成立

x*x = x (mod n)

n = q*p

x*(x-1) = (a*b)*(q*p) , a, b为整数

(1)x = a*q, x-1 = b*p,

a*q +b*p = x + (x-1) = 1;

用拓展欧几里得算法求出a, b， x3 = a*q;

(2) x-1 = a*q, x = b*p

x4 = b*p

  1 #include <iostream>
  2 #include <sstream>
  3 #include <fstream>
  4 #include <string>
  5 #include <vector>
  6 #include <deque>
  7 #include <queue>
  8 #include <stack>
  9 #include <set>
 10 #include <map>
 11 #include <algorithm>
 12 #include <functional>
 13 #include <utility>
 14 #include <bitset>
 15 #include <cmath>
 16 #include <cstdlib>
 17 #include <ctime>
 18 #include <cstdio>
 19 #include <cstring>
 20 #define FOR(i, a, b)  for(int i = (a); i <= (b); i++)
 21 #define RE(i, n) FOR(i, 1, n)
 22 #define FORP(i, a, b) for(int i = (a); i >= (b); i--)
 23 #define REP(i, n) for(int i = 0; i <(n); ++i)
 24 #define SZ(x) ((int)(x).size )
 25 #define ALL(x) (x).begin(), (x.end())
 26 #define MSET(a, x) memset(a, x, sizeof(a))
 27 using namespace std;
 28 
 29 
 30 typedef long long int ll;
 31 typedef pair<int, int> P;
 32 int read() {
 33     int x=0,f=1;
 34     char ch=getchar();
 35     while(ch<'0'||ch>'9') {
 36         if(ch=='-')f=-1;
 37         ch=getchar();
 38     }
 39     while(ch>='0'&&ch<='9') {
 40         x=x*10+ch-'0';
 41         ch=getchar();
 42     }
 43     return x*f;
 44 }
 45 const double pi=3.14159265358979323846264338327950288L;
 46 const double eps=1e-6;
 47 const int mod = 1e9 + 7;
 48 const int INF = 0x3f3f3f3f;
 49 const int MAXN = 100005;
 50 const int xi[] = {0, 0, 1, -1};
 51 const int yi[] = {1, -1, 0, 0};
 52 
 53 int N, T;
 54 int a[MAXN], prime[MAXN], cnt;
 55 void init() {
 56     cnt = 0;
 57     for(int i = 2; i < MAXN; i++) a[i] = true;
 58     for(int i = 2; i < MAXN; i++) {
 59         if(a[i]) {
 60             prime[++cnt] = i;
 61         }
 62         for(int j = 1; j <= cnt; j++) {
 63             if(i*prime[j] >= MAXN) break;
 64             a[i*prime[j]] = false;
 65             if(i%prime[j] == 0) break;
 66         }
 67     }
 68 }
 69 int exgcd(int a, int b, int &x, int &y) {
 70     int d = a;
 71     if(b != 0) {
 72         d = exgcd(b, a%b, y, x);
 73         y -= (a/b)*x;
 74     } else {
 75         x = 1, y = 0;
 76     }
 77     return d;
 78 }
 79 int main() {
 80     //freopen("in.txt", "r", stdin);
 81     init();
 82     int t, n;
 83     scanf("%d", &t);
 84     while(t--) {
 85         scanf("%d", &n);
 86         int p = - 1, q = -1;
 87         for(int i = 1; i <= cnt; i++) {
 88             if(n%prime[i] == 0) {
 89                 int k = n/prime[i];
 90                 int flag = 1;
 91                 for(int j = 2; j*j <= k; j++){
 92                     if(k%j == 0){
 93                         flag = 0;
 94                         break;
 95                     }
 96                 }
 97                 if(flag){
 98                     p = prime[i], q = n/prime[i];
 99                     break;
100                 }
101             }
102         }
103       //  printf("%d %d
", p, q);
104         //  if(p > q) swap(p, q);
105         int x, y, res1, res2, d;
106         d = exgcd(p, q, x, y);
107        // printf("%d %d
", x, y);
108         res1 = p*x;
109         if(res1 <= 0) res1 += n;
110       //  printf("%d
",res1);
111         d = exgcd(q, p, x, y);
112        // printf("%d %d
", x, y);
113         res2 = q*x;
114         if(res2 <= 0) res2 += n;
115         //printf("%d
", res2);
116         if(res2 < res1) swap(res1, res2);
117         printf("0 1 %d %d
", res1, res2);
118     }
119     return 0;
120 }