STEP5 0051 Ch特別篇-5.數學作業2

[MATH]

分解成質數的冪次後就AC了XDD

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define NN 1000010
#define LL long long int
bool seive[NN+10];
vector<LL> PRIME;
vector<LL> Conds;
vector<LL> Ins;
void maketable()
{
memset(seive,false,sizeof(seive));
for(int lx=2;lx<=NN;lx++)
{
if(seive[lx]==false)
{
PRIME.push_back((LL)lx);
for(int ly=2;ly*lx<=NN;ly++)
seive[ly*lx]=true;
}
}
}
void add(LL II)
{
bool Exist=false;
for(int lx=0;lx<Conds.size();lx++)
if(Conds[lx]%II==0)
return;
else if(II%Conds[lx]==0)
{
Conds.erase(Conds.begin()+lx);
Conds.push_back(II);
return;
}
Conds.push_back(II);
}
int main()
{
maketable();
int N;scanf("%d",&N);
for(int lx=0;lx<N;lx++)
{
LL I;scanf("%I64d",&I);
Ins.push_back(I);
for(int lx=0;(lx<PRIME.size())&&(PRIME[lx]<I);lx++)
{
if(I%PRIME[lx]==0)
{
//printf("PRIME=%I64d\n",PRIME[lx]);
LL a=1;
while(I%PRIME[lx]==0)
{
a*=PRIME[lx];
I/=PRIME[lx];
}
add(a);
}
}
if(I>1)
add(I);
}
#ifdef DEBUG
for(int lx=0;lx<Conds.size();lx++)
printf("%I64d ",Conds[lx]);
#endif
LL match[1000];
for(int lx=0;lx<N;lx++)
match[lx]=1;
for(int lx=0;lx<Conds.size();lx++)
{
for(int ly=0;ly<Ins.size();ly++)
if(Ins[ly]%Conds[lx]==0)
{
match[ly]*=Conds[lx];
break;
}
}
for(int lx=0;lx<N;lx++)
printf("%I64d ",match[lx]);
return 0;
}