Кресты / Говнокод #13419 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
#include<iostream>
#include<set>
#include<vector>
#include<hash_set>
#include<math.h>
#include<stdlib.h>
using namespace std;
inline int po(int a,int b){
int ans =1;
for(int i=0;i<b;++i)ans*=a;
return ans;
}
inline bool isnotsq(int a){
	return sqrt(0.0+a)!=int(sqrt(a+0.0));
}

int main(){
	int t,n,k;
	cin>>t;
	int SQRT  = 100000,primes[100100]={0};
	primes[2]=1;
	vector<int> pr;
	pr.push_back(2);
	for(int i = 3;i<=SQRT;i+=2){
		if(primes[i]==0) {
			pr.push_back(i);
			for(int j = 2*i;j<=SQRT;j+=i) primes[j]=1;
		}
	}
	while(t--){
		cin>>n>>k;
		int nn=n;
		int divisors[1001];
		int divisecount[1001]={0};
		int divc=0;
		int count = 0;
		for(int i =0;i<pr.size();++i){
			if(n%pr[i]==0) divisors[divc++]=pr[i];
			while(n%pr[i]==0) divisecount[divc-1]++,n/=pr[i],count++;
		}
		if(n!=1) divisors[divc++]=n,divisecount[divc-1]=1;
		//for(int i =0;i<divc;++i) cout<<divisors[i]<<' '<<divisecount[i]<<'\n';
		vector< int> cbused;
		vector<int> rem;
		rem.push_back(0);
		cbused.push_back(1);
		
		for(int i =0;i<divc;++i){
			int cs = cbused.size();
			for(int j =0;j<cs;++j){
				int cc = divisors[i];
				int ops=1;
				while(1){
					if(nn%(cbused[j]*cc)==0) {
						if(isnotsq(cbused[j]*cc)) 
							cbused.push_back(cbused[j]*cc),rem.push_back(rem[j]+ops);
					}
					else break;
					cc*=divisors[i];
					ops+=1;
				}
 			}
		}
		//for(int  i = 0;i<cbused.size();++i) cout<<cbused[i]<<' '<<rem[i]<<'\n';
		int siz= cbused.size();
		set< pair<int,int > > anse;
		anse.insert(make_pair(1,0));
		for(int j = 1;j<siz;++j){
			for(int i = cbused[j],k=1;nn%i==0;i*=cbused[j],k++) if(i%2==1) anse.insert(make_pair(i,k));
		}
		for(int i = 1;i<siz;++i){
				vector<pair<int , int> > toa;
				for(set< pair<int,int> >::iterator it=anse.begin();it!=anse.end();it++){
					if(nn%(cbused[i]*it->first)==0&&it->second<k) toa.push_back(make_pair(cbused[i]*it->first,it->second+1));
					for(int q=0;q<toa.size();q++) anse.insert(toa[q]);
				}
			}
		
		bool f = false;
		for(set< pair<int,int> >::iterator it=anse.begin();it!=anse.end();it++){
			if(it->first==nn&&it->second==k) f=true;
		}
		cout<<(f?"YES":"NO")<<"\n";
		if(t==0) return 0;
	}
}

Задано целое положительное число n. Выясните, может ли оно быть представлено в виде произведения k целых положительных чисел, ни одно из которых не является квадратом целого числа.
(с яндекс.алгоритма)

Запостил: AvadaKedavra AvadaKedavra, (Updated )

Комментарии (14) RSS

Добавить комментарий

Помни, guest, за тобой могут следить!

    А не использовать ли нам bbcode?

    ↑
    8
    ↓