bzoj 1053 [HAOI2007]反素数ant——关于质数的dfs / 打表
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1053
写了个打表程序。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int lst=1,cnt,N=2e9,fx=2,knt; int main() { for(int i=2;i<=N;i+=fx) { cnt=1;int k=i; for(int j=2;j*j<=k;j++) { int ct=0; if(k%j==0) { if(j!=2&&(j&1)==0){cnt=2;break;} while(k%j==0)k/=j,ct++; } cnt*=ct+1; } if(k>1)cnt<<=1; if(cnt>lst)printf("%d ",i),lst=cnt,knt++; if(i==60)fx=10; if(i==2520)fx=120; if(i==1441440)fx=240; } return 0; }
打了个表过了……
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; int c[75]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560, 10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200, 332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320, 6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720, 43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800, 294053760,367567200,551350800,698377680,735134400,1102701600,1396755360}; int main() { scanf("%d",&n); for(int i=67;i>=0;i--) if(c[i]<=n) { printf("%d ",c[i]);break; } return 0; }