Submission #846686


Source Code Expand

Copy
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<algorithm>
#include<map>
using namespace std;
#define BigInteger long long int

BigInteger FACTORLIST[50];
int EXPONENTLIST[50],BIGOMEGA;

int smallprimes[168]={
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,
59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,
137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,
227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,
313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,
509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,
617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,
727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,
829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997};
/* small table */

BigInteger powmod(BigInteger,BigInteger,BigInteger);
int strong_pseudo_primetest(BigInteger,int);
int isprime(BigInteger);
BigInteger gcd(BigInteger,BigInteger);
void factor_using_pollard_rho (BigInteger n,int);
void factor(BigInteger n);

BigInteger mulmod(const BigInteger&a, const BigInteger&b, const BigInteger&p)
{
	long long int y = (long long int)((double)a*(double)b/p+0.5);
	long long int  r=a*b-y*p;
	if (r<0) r = r+p;

	return r;
//	return a*b%p;
}

BigInteger powmod(BigInteger n,BigInteger exponent,BigInteger modulus)  {
/* return by (n^exponent)%modulus, here exponent>=0 */
	
	BigInteger result=1,powres=n%modulus;
	
	while(exponent>0)  {
		  if(exponent%2==1)result=mulmod(result,powres,modulus);
		  powres=mulmod(powres,powres,modulus);
		  exponent/=2;
	}
	return result;
}

int strong_pseudo_primetest(BigInteger n,int base)  {
/* return by 1 if n is a strong pseudo prime for base, otherwise by 0 */
	
	BigInteger n2=n-1,res;
	int s;
	s=0;

	while(n2%2==0)  n2/=2,s++;
	
	res=powmod(base,n2,n);
	if((res==1)||(res==n-1))  return 1;
	
	s--;
	while(s>=0)  {
		res=mulmod(res,res,n);
		if(res==n-1)  return 1;
		s--;
	}
	return 0;
}

int isprime(BigInteger n)  {
	if(n<2)  return 0; 
	if(n<4)  return 1; 

	if(strong_pseudo_primetest(n,2)==0)  return 0;
	if(strong_pseudo_primetest(n,3)==0)  return 0;
	if(n<1373653LL)  return 1;
	if(strong_pseudo_primetest(n,5)==0)  return 0;
	if(n<25326001LL)  return 1;
	if(strong_pseudo_primetest(n,7)==0)  return 0;
	if(n==3215031751LL)  return 0;
	if(n<25000000000LL)  return 1;
	if(strong_pseudo_primetest(n,11)==0)  return 0;
	if(n<2152302898747LL)  return 1;
	if(strong_pseudo_primetest(n,13)==0)  return 0;
	if(n<3474749660383LL)  return 1;
	if(strong_pseudo_primetest(n,17)==0)  return 0;
	if(n<341550071728321LL)  return 1;
	if(strong_pseudo_primetest(n,19)==0)  return 0;
	if(strong_pseudo_primetest(n,23)==0)  return 0;
	if(strong_pseudo_primetest(n,29)==0)  return 0;
	if(strong_pseudo_primetest(n,31)==0)  return 0;
	if(strong_pseudo_primetest(n,37)==0)  return 0;
	return 1; 
	/* are we sure that n is prime?! Up to 2^63 there can be some exceptions, but very few. */
}

BigInteger gcd(BigInteger a,BigInteger b)
{
 BigInteger c;
 if(a==0)  return b;
 if(b==0)  return a;

 while(b>0)
 {
	 a%=b;
	 c=a;
	 a=b;
	 b=c;
 }
 return a;
}

void factor_using_pollard_rho (BigInteger n,int a)  {
/* factorization by Pollard method x -> (x^2+a)%n is the sequence in the factorization */
	BigInteger y,x,x1,g,P,t1;
	int c,i,k,l,expo,count,err;
	y=2;
	x=2;
	x1=2;
	k=1;
	l=1;
	P=1;
	c=0;
	
	while(n!=1)  {
		  S2:
			 x=mulmod(x,x,n);
			 x=(x+a)%n;
			 t1=n+x1-x;
			 if(t1>=n)t1-=n;
			 P=mulmod(P,t1,n);
			 
			 c++;
			 if(c==20)  {
				c=0;
				g=gcd(P,n);
				if(g!=1)  goto S4;
				y=x;
			 }
		  S3:
			 k--;
			 if(k>0)  goto S2;
			 
			 g=gcd(P,n);
			 if(g!=1)  goto S4;
			 
			 x1=x;
			 k=l;
			 l=2*l;
			 for(i=0;i<k;i++)
			 {
				 x=mulmod(x,x,n);
				 x=(x+a)%n;
			 }
			 y=x;
			 c=0;
			 goto S2;
		   S4:
			 err=0;
			 count=0;
			 do {
				if(count>l)  {
				   err=1;
				   break;
				}
				y=mulmod(y,y,n);
				y=(y+a)%n;
				t1=n+x1-y;
				if(t1>=n) t1-=n;
				g=gcd(t1,n);
				count++;
			 }
			 while(g==1);
			 
			 if(err==1)  {
				do {
					a=rand();
				}
				while(a<4);
				factor_using_pollard_rho(n,a);
				break;
			 }
			 else {
			 n=n/g;
			 if(isprime(g)==0)  {
				do {
				   a=rand();
				}
				while(a<4);
			 
				factor_using_pollard_rho(g,a);
			 }
			 else {
				expo=1;
				while(n%g==0)  n/=g,expo++;
				FACTORLIST[BIGOMEGA]=g;
				EXPONENTLIST[BIGOMEGA]=expo;
				BIGOMEGA++;
			 }
			 }
			 x=mulmod(x,x,n);
			 if(isprime(n)==1)  {
				FACTORLIST[BIGOMEGA]=n;
				EXPONENTLIST[BIGOMEGA]=1;
				BIGOMEGA++;
				n=1;
			 }
	  }
	  return;
}

void factor(BigInteger n)  {
	int i,expo;
	/* trial divide by the first 168 primes (primes up to 1000) */
	BIGOMEGA=0;
	if(n<2)  return;
	
	for(i=0;(i<168)&&(smallprimes[i]*smallprimes[i]<=n);i++)  {
		if(n%smallprimes[i]==0)  {
		   n/=smallprimes[i],expo=1;
		   while(n%smallprimes[i]==0)  n/=smallprimes[i],expo++;
		   FACTORLIST[BIGOMEGA]=smallprimes[i];
		   EXPONENTLIST[BIGOMEGA]=expo;
		   BIGOMEGA++;
		}
	}
	if(n==1)  return;
	if((n<1000000)||(isprime(n)==1)) {
	   FACTORLIST[BIGOMEGA]=n;
	   EXPONENTLIST[BIGOMEGA]=1;
	   BIGOMEGA++;
	   return;
	}
	/* at here we know n is composite */
	factor_using_pollard_rho(n,3);
}

#include<iostream>
#include<vector>
map<vector<long long int>,int> Map;
bool cmp(long long int x,long long int y){
	return (x>0?x:-x) < (y>0?y:-y);
}
int main()
{
	int _;
	BigInteger n;
	srand(time(0));
	for(cin>>_; _--;)
	{
		cin>>n;
		factor(n);
		vector<long long int> v;
		for(int i=0; i<BIGOMEGA; i++){
			EXPONENTLIST[i] %= 3;
			if(EXPONENTLIST[i] == 1)
				v.push_back(FACTORLIST[i]);
			else
			if(EXPONENTLIST[i] == 2)
				v.push_back(-FACTORLIST[i]);
		}
		sort(v.begin(),v.end(),cmp);
		Map[v]++;
	}
	vector<long long int> v;
	int res = 0;
	if(Map.count(v)){
		res ++;
		Map.erase(v);
	}
	int res2 = 0;
	for(map<vector<long long int>,int>::iterator it = Map.begin(); it != Map.end(); it++){
		vector<long long int> v1 = it->first;
		int w = it->second;
		for(int i=0; i<v1.size(); i++)
			v1[i] = -v1[i];
		if(Map.count(v1)){
			w = max(w, Map[v1]);
			Map.erase(v1);
		}
		res2 += w;
	}
	cout << res2 + res << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Anticube
User maryanna2016
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 6547 Byte
Status AC
Exec Time 1056 ms
Memory 11904 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 3
AC × 51
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 1036 ms 11904 KB
02.txt AC 1029 ms 11904 KB
03.txt AC 1032 ms 11904 KB
04.txt AC 1032 ms 11904 KB
05.txt AC 1033 ms 11904 KB
06.txt AC 1035 ms 11904 KB
07.txt AC 1034 ms 11904 KB
08.txt AC 1033 ms 11904 KB
09.txt AC 1056 ms 11904 KB
10.txt AC 1047 ms 11904 KB
11.txt AC 872 ms 3712 KB
12.txt AC 870 ms 3712 KB
13.txt AC 845 ms 4352 KB
14.txt AC 846 ms 4352 KB
15.txt AC 854 ms 4352 KB
16.txt AC 854 ms 4352 KB
17.txt AC 172 ms 256 KB
18.txt AC 171 ms 256 KB
19.txt AC 174 ms 256 KB
20.txt AC 172 ms 256 KB
21.txt AC 766 ms 7040 KB
22.txt AC 754 ms 7040 KB
23.txt AC 770 ms 7168 KB
24.txt AC 756 ms 7040 KB
25.txt AC 763 ms 7040 KB
26.txt AC 759 ms 7040 KB
27.txt AC 243 ms 9600 KB
28.txt AC 33 ms 256 KB
29.txt AC 44 ms 256 KB
30.txt AC 67 ms 256 KB
31.txt AC 67 ms 256 KB
32.txt AC 67 ms 256 KB
33.txt AC 4 ms 256 KB
34.txt AC 177 ms 256 KB
35.txt AC 146 ms 256 KB
36.txt AC 4 ms 256 KB
37.txt AC 855 ms 4480 KB
38.txt AC 853 ms 4480 KB
39.txt AC 854 ms 4480 KB
40.txt AC 862 ms 4480 KB
41.txt AC 4 ms 256 KB
42.txt AC 4 ms 256 KB
43.txt AC 6 ms 256 KB
44.txt AC 4 ms 256 KB
45.txt AC 4 ms 256 KB
46.txt AC 4 ms 256 KB
47.txt AC 4 ms 256 KB
48.txt AC 4 ms 256 KB
s1.txt AC 4 ms 256 KB
s2.txt AC 4 ms 256 KB
s3.txt AC 4 ms 256 KB