SGU 200.Cracking RSA（ガウスの消元は自由元の個数を求める）
25981 ワード
テーマリンク:http://acm.sgu.ru/problem.php?contest=0&problem=200
200.Cracking RSA
time limit per test：0.25 sec.
memory limit per test：65536 KB
input:standard
out put:standard
The follwing problem is somehow related to the final stage of many famous integer factoriation algorithms involved in some cryptanlytical probles，for example cracking well-known RSA public system.
The most powerful of such algorithms、so caled quadratic sieve descendant algorithms、utilize the fact that if n=p q where p and q are unknown predtobe found、then if v
2=w
2 (mod n)、u≠v(mod n)and u≠v(mod n)、then gcd(v+w，n)is a factor of n(ether p or q)
Not getting Frther in the details of these algorithms，let us consider our proble m.Gven m integer numbers b
1,b
2,…，b
m such that all their preme factors are from the set of first prmes，the task is to find such a subset S of｛1，2，…，m｝that product of b
i for i from S is a perfect square i.e.equal to u
2 for some integer u.Given such S we get one pair for testing(product of S elemens stands stands forevwhen w w w w w w w w w isknowwn ffrom otheeps of algorithms which arar of no interest to us、testing perperformed ischchchchchewheheheheckinininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininm possible probability、we would like to get as many such sets as possible.So the interesting problem could be to calculate the number of all such sets.This exactly your task.
Input
The first line of the input file contains two integers t and m(1≦t≦100,1≦m≦100).The second line of the input file contains m integer numbers b
i such that all their prive factors are from t first premens(for example、if t=3 all their prive factors are from the set｛2，3，5｝.1≦b
i ≦10
9 for all i.
Output
Output the number of non-empty subsets of the given set{b
i}the product of numbers from which is a perfect square
Sample test(s)
Input
3 4 9 20,500 3
Output
3
この問題はm個の数を与えています。このm個の数の質因子は全部前のt個の素数からなります。
このm個の数のサブセットがいくつかありますか？それらの積は完全な平方数になります。
完全な平方数とは、各素数の指数が偶数であることを要求する。
各質量因子に対して方程式を構築した。モード2の線形方程式群となる。
この方程式グループを解くには何個の自由変数がありますか？答えは2^ret-1で、空セットを取り除く場合です。
200.Cracking RSA
time limit per test：0.25 sec.
memory limit per test：65536 KB
input:standard
out put:standard
The follwing problem is somehow related to the final stage of many famous integer factoriation algorithms involved in some cryptanlytical probles，for example cracking well-known RSA public system.
The most powerful of such algorithms、so caled quadratic sieve descendant algorithms、utilize the fact that if n=p q where p and q are unknown predtobe found、then if v
2=w
2 (mod n)、u≠v(mod n)and u≠v(mod n)、then gcd(v+w，n)is a factor of n(ether p or q)
Not getting Frther in the details of these algorithms，let us consider our proble m.Gven m integer numbers b
1,b
2,…，b
m such that all their preme factors are from the set of first prmes，the task is to find such a subset S of｛1，2，…，m｝that product of b
i for i from S is a perfect square i.e.equal to u
2 for some integer u.Given such S we get one pair for testing(product of S elemens stands stands forevwhen w w w w w w w w w isknowwn ffrom otheeps of algorithms which arar of no interest to us、testing perperformed ischchchchchewheheheheckinininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininm possible probability、we would like to get as many such sets as possible.So the interesting problem could be to calculate the number of all such sets.This exactly your task.
Input
The first line of the input file contains two integers t and m(1≦t≦100,1≦m≦100).The second line of the input file contains m integer numbers b
i such that all their prive factors are from t first premens(for example、if t=3 all their prive factors are from the set｛2，3，5｝.1≦b
i ≦10
9 for all i.
Output
Output the number of non-empty subsets of the given set{b
i}the product of numbers from which is a perfect square
Sample test(s)
Input
3 4 9 20,500 3
Output
3
この問題はm個の数を与えています。このm個の数の質因子は全部前のt個の素数からなります。
このm個の数のサブセットがいくつかありますか？それらの積は完全な平方数になります。
完全な平方数とは、各素数の指数が偶数であることを要求する。
各質量因子に対して方程式を構築した。モード2の線形方程式群となる。
この方程式グループを解くには何個の自由変数がありますか？答えは2^ret-1で、空セットを取り除く場合です。
1 /* ***********************************************
2 Author :kuangbin
3 Created Time :2014-1-20 9:19:03
4 File Name :E:\2014ACM\SGU\SGU200.cpp
5 ************************************************ */
6
7 #include <stdio.h>
8 #include <string.h>
9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 using namespace std;
18
19 //
20 void add(char a[],char b[],char c[])
21 {
22 int len1 = strlen(a);
23 int len2 = strlen(b);
24 int len = max(len1,len2);
25 int up = 0;
26 for(int i = 0;i < len;i++)
27 {
28 int tmp = 0;
29 if(i < len1) tmp += a[i] - '0';
30 if(i < len2) tmp += b[i] - '0';
31 tmp += up;
32 c[i] = tmp%10 + '0';
33 up = tmp/10;
34 }
35 if(up)
36 c[len++] = up + '0';
37 c[len] = 0;
38 }
39 void SUB_ONE(char a[])
40 {
41 int id = 0;
42 while(a[id] == '0')id++;
43 a[id]--;
44 for(int i = 0;i < id;i++)
45 a[i] = '9';
46 int len = strlen(a);
47 while(len > 1 && a[len-1] == '0')len--;
48 a[len] = 0;
49 }
50
51 int equ,var;
52 int a[110][110];
53 int x[110];
54 int free_x[110];
55 int free_num;
56
57 // -1 ， 0 ，
58 int Gauss()
59 {
60 int max_r, col, k;
61 free_num = 0;
62 for(k = 0, col = 0; k < equ && col < var; k++, col++)
63 {
64 max_r = k;
65 for(int i = k+1 ; i < equ; i++)
66 if(abs(a[i][col]) > abs(a[max_r][col]))
67 max_r = i;
68 if(a[max_r][col] == 0)
69 {
70 k--;
71 free_x[free_num++] = col; //
72 continue;
73 }
74 if(max_r != k)
75 {
76 for(int j = col; j < var+1; j++)
77 swap(a[k][j],a[max_r][j]);
78 }
79 for(int i = k+1; i < equ;i++)
80 if(a[i][col] != 0)
81 for(int j = col; j < var+1;j++)
82 a[i][j] ^= a[k][j];
83 }
84 for(int i = k;i < equ;i++)
85 if(a[i][col] != 0)
86 return -1;
87 if(k < var)return var-k;
88 for(int i = var-1; i >= 0;i--)
89 {
90 x[i] = a[i][var];
91 for(int j = i+1; j < var;j++)
92 x[i] ^= (a[i][j] && x[j]);
93 }
94 return 0;
95 }
96
97 const int MAXN = 1000;
98 int prime[MAXN+1];
99 void getPrime()
100 {
101 memset(prime,0,sizeof(prime));
102 for(int i = 2;i <= MAXN;i++)
103 {
104 if(!prime[i])prime[++prime[0]] = i;
105 for(int j = 1;j <= prime[0] && prime[j] <= MAXN/i;j++)
106 {
107 prime[prime[j]*i] = 1;
108 if(i%prime[j] == 0)break;
109 }
110 }
111 }
112
113 int b[110];
114 char str1[110],str2[110];
115
116 int main()
117 {
118 //freopen("in.txt","r",stdin);
119 //freopen("out.txt","w",stdout);
120 getPrime();
121 int t,m;
122 while(scanf("%d%d",&t,&m) != EOF)
123 {
124 for(int i = 0;i < m;i++)
125 scanf("%d",&b[i]);
126 equ = t;
127 var = m;
128 for(int i = 0;i < t;i++)
129 for(int j = 0;j < m;j++)
130 {
131 int cnt = 0;
132 while(b[j]%prime[i+1] == 0)
133 {
134 cnt++;
135 b[j] /= prime[i+1];
136 }
137 a[i][j] = (cnt&1);
138 }
139 for(int i = 0;i < t;i++)
140 a[i][m] = 0;
141 int ret = Gauss();
142 strcpy(str1,"1");
143 for(int i = 0;i < ret;i++)
144 {
145 add(str1,str1,str2);
146 strcpy(str1,str2);
147 }
148 SUB_ONE(str1);
149 int len = strlen(str1);
150 for(int i = len-1;i >= 0;i--)
151 printf("%c",str1[i]);
152 printf("
");
153 }
154 return 0;
155 }