首页 > 代码库 > sgu200--Cracking RSA(高斯消元问题5，求乘积为完全平方数的种数)
sgu200--Cracking RSA(高斯消元问题5，求乘积为完全平方数的种数)
Cracking RSA
Time Limit:250MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
<ｓcript type="text/javaｓcript" language="javaｓcript" src=http://www.mamicode.com/"http://acm.sgu.ru/js/jquery.js"><ｓcript type="text/javaｓcript" language="javaｓcript" src="http://acm.sgu.ru/js/jquery.example.js"><ｓcript type="text/javaｓcript" language="javaｓcript" src="http://acm.sgu.ru/js/ui.datepicker.js"><ｓcript>
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
200. Cracking RSA
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
memory limit per test: 65536 KB
input: standard
output: 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.
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
3
给出n个数，每个数都是由前t个素数组成的，问成绩为完全平方数的子集有多少？
完全平方数，也就是所成绩的所有素数组成都是偶数个，由此可以列出方程组，方程为Map[i][j]第j个数的第i个素数个数是不是偶数，偶数为0，奇数为1，结果全部为0，找出一共有多少组，也就是说找出自由元数num1，然后2^num1 - 1，减去全为0的一组，就是结果。
注意1，求自由元的时候不能直接在j == n的时候计数，那样在n*n的矩阵中可以，如果不是的话要用n-i
注意2，求出的自由元会很大，2^num1是个大数，所以要模拟一下，因为2的倍数的最后一位是1,2,4,8,6,2,....所以最后直接将最后一位减一就可以了
#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;int vis[1100] , prim[1100] , cnt ;int Map[110][110] , a[110] ;int s[10000] ;void get_prim(){ int i , j ; memset(vis,0,sizeof(vis)) ; memset(prim,0,sizeof(prim)) ; cnt = 0 ; for(i = 2 ; i < 1000 ; i++) { if( !vis[i] ) { prim[cnt++] = i ; } for(j = 0 ; j < cnt ; j++) { if( prim[j]*i >= 1000 ) break ; vis[ prim[j]*i ] = 1 ; if( i % prim[j] == 0 ) break ; } } return ;}void swap1(int p,int q,int m){ int i , temp ; temp = a[p] ; a[p] = a[q] ; a[q] = temp ; for(i = 0 ; i < m ; i++) { temp = Map[p][i] ; Map[p][i] = Map[q][i] ; Map[q][i] = temp ; } return ;}int gauss(int n,int m){ int i , j , k , t , num1 = 0; for(i = 0 , t = 0 ; i < n && t < m ; i++ , t++) { for(j = i ; j < n ; j++) if( Map[j][t] ) break ; if( j == n ) { i-- ; continue ; } if( i != j ) swap1(i,j,m) ; for(j = i+1 ; j < n ; j++) { if( Map[j][t] == 0 ) continue ; a[j] ^= a[i] ; for(k = t ; k < m ; k++) { Map[j][k] ^= Map[i][k] ; } } } return m - i ;}int main(){ int t , m , i , j , x , num1 ; get_prim() ; memset(Map,0,sizeof(Map)) ; scanf("%d %d", &t, &m) ; for(j = 0 ; j < m ; j++) { scanf("%d", &x) ; for(i = 0 ; i < t ; i++) { a[i] = 0 ; num1 = 0 ; while( x % prim[i] == 0 ) { num1++ ; x /= prim[i] ; } Map[i][j] = num1 % 2 ; } } num1 = gauss(t,m) ; s[0] = 1 ; cnt = 1 ; int temp , k ; for(i = 0 ; i < num1 ; i++) { temp = 0 ; for(j = 0 ; j < cnt ; j++) { k = s[j]*2 + temp ; s[j] = k%10 ; temp = k/10 ; } if( temp != 0 ) s[cnt++] = temp ; } s[0] -= 1 ; for(i = cnt-1 ; i >= 0 ; i--) { printf("%d", s[i]) ; } printf("\n") ; return 0;}sgu200--Cracking RSA(高斯消元问题5，求乘积为完全平方数的种数)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。