Main » 2013 October 14 » [NOIP2012模拟赛No.22]完全平方数
11:21 AM [NOIP2012模拟赛No.22]完全平方数 |
这道题的关键是快速分解质因数 可以预处理出每个数最小的因子 然后依次除以它 #include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 1000100 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int cnt=0,c[N]; bool f[N]; void init() { int i,j; FOR(i,2,N) FOR(j,1,N/i) if (!c[i*j]) c[i*j]=i; } void resolve(int x) { while (x>1) { f[c[x]]=!f[c[x]]; if (f[c[x]]) cnt++; else cnt--; x/=c[x]; } } int main() { init(); int n,i,X; scanf("%d",&n); FOR(i,1,n) { scanf("%d",&X); resolve(X); if (cnt==0) printf("DA\n"); else printf("NE\n"); } } |
|
|
| Total comments: 0 | |