SGU 200. Cracking RSA （高斯消元求自由变元个数）

向右看齐 2022-03-27 14:50 108阅读 0赞

题目链接：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  
output: standard

The following problem is somehow related to the final stage of many famous integer factorization algorithms involved in some cryptoanalytical problems, for example cracking well-known RSA public key system.  
  
The most powerful of such algorithms, so called quadratic sieve descendant algorithms, utilize the fact that if n = pq where p and q are large unknown primes needed to be found out, 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 (either p or q).  
  
Not getting further in the details of these algorithms, let us consider our problem. Given m integer numbers b 1, b 2, ..., b m such that all their prime factors are from the set of first t primes, 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 elements stands for v when w is known from other steps of algorithms which are of no interest to us, testing performed is checking whether pair is nontrivial, i.e. u ≠ v (mod n) and u ≠ -v (mod n)). Since we want to factor n with maximum 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 is 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 prime factors are from t first primes (for example, if t = 3 all their prime 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

这题就是给出了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("\n");
    153     }
    154     return 0;
    155 }