StrangeStandard

  一道反素数的题目，求的是区间内的最大反素数。一开始做我是打表的(而且这表还不是自己打出来的),代码如下:

#include <cstdio> 
#include <iostream> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#include <vector>
#include <list>
#include <string>
#include <queue>
#include <assert.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int ans[200]={2000000001,1396755360,1102701600,735134400,698377680,
551350800,367567200,294053760,245044800,
183783600,147026880,122522400,110270160,
73513440,61261200,43243200,36756720,
32432400,21621600,17297280,14414400,10810800,
8648640,7207200,6486480,4324320,3603600,2882880,
2162160,1441440,1081080,720720,665280,554400,498960,
332640,277200,221760,166320,110880,83160,55440,50400,
45360,27720,25200,20160,15120,10080,7560,5040,2520,1680,
1260,840,720,360,240,180,120,60,48,36,24,12,6,4,2,1,0};
int main()
{
    int n;
    int t;cin>>t;
    int kase=0;
    while(t--)
    {
        cin>>n;
        for(int i=0;;i++)
            if(ans[i]<=n)
            {
                printf("Case #%d: %d\n",++kase,ans[i]);
                break; 
            }
    }
    return 0;
}

  这题非打表的方法是用dfs。具体代码如下:

#include <cstdio> 
#include <iostream> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#include <vector>
#include <list>
#include <string>
#include <queue>
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=500005;
ll n,ans;
ll maxi=-1;
ll prime[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
void dfs(int dep,int now,int cnt)
{    
    if(dep>=16)
        return ;
    if(cnt==maxi&&ans>now)
        ans=now;
    if(cnt>maxi)
    {
        maxi=cnt;
        ans=now;
    }
    for(int i=1;i<=100;i++)
    {    
        if(now*prime[dep]>n)        break;
        now*=prime[dep];
        dfs(dep+1,now,cnt*(i+1));
    }
    return ;
}
int main()
{    
    int t;
    cin>>t;
    int kase=0;
    while(t--)
    {    
        ans=0;maxi=-1;
        cin>>n;
        dfs(0,1,1);
        printf("Case #%d: %lld\n",++kase,ans);
    }
    return 0;
}