- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 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 целых положительных чисел, ни одно из которых не является квадратом целого числа.
(с яндекс.алгоритма)
Follow us!
k не превосходит количество простых сомножителей в разложении n.
Если n — степень простого, то чётность k совпадает с чётностью показателя.
Отдельный минус за использование нестандартного расширения студии.
AvadaKedavra, никак Гари Поттера пересмотрела?
Ok, буду unordered юзать
PS. еще, блин, Империо сюда надо ...
(тупое и тормознутое)
текст условия задача С отсюда http://yadi.sk/d/eoqM9n1p7Cvou
задача С - неквадраты
пробел лишний, когда пишу его нет, после отправки появляется
https://disk.yandex.ru/public/?hash=R7Y2li9a0LsJTucoSv9jCdy0djla8CzXD9Cb/FrB0VM%3D