题目背景
正整数n是无穷的,但其中有些数有神奇的性质,我们给它个名字——AP数。
题目描述
对于一个数字i是AP数的充要条件是所有比它小的数的因数个数都没有i的因数个数多。比如6的因数是1 2 3 6 共计有4个因数。它就是一个AP数(1-5的因数个数不是2就是3)。我们题目的任务就是找到一个最大的,且不超过n的AP数。
输入输出格式
输入格式:
每个测试点可能拥有多组数据。
对于每一行有一个n,如题目所描述
输出格式:
对于每一行输出最大的且不超过n的AP数
#include<cmath> #include<cstdio> #include<iostream> using namespace std; long long n,ap,fap; int mm[30]={2,3,5,7,11,13,17,19,23,29}; void dfs(long long num,long long fnum,long long i,long long j) { if(fap<fnum||(fap==fnum&&ap>num)) { fap=fnum; ap=num; } int t=1; while(t<=j&&num*mm[i]<=n) { num*=mm[i]; dfs(num,fnum*(t+1),i+1,t); t++; } return; } int main() { while(~scanf("%lld",&n)) { ap=0; fap=0; dfs(1,1,0,20); cout<<ap<<endl; } } // ap=ap/3; // ap=ap*3; // ap=ap/11; // ap=ap*11;