P1820 【寻找AP数】

超级题目链接

这题程序实现其实并不难，难的是数学的思想及证明，这在真正的比赛考场上其实是不容易想到的

去年的年赛题目也是在往更难的数学思想上靠拢，并不是一味的编程，需要一定的数学基础

这个。。数学性质我再提一下吧，有兴趣的可以自己尝试证一下~~

_性质一_

一个AP数分解质因数后，它的因子必为连续质数

_性质二_

一个AP数分解质因数后，因子越小，指数越大

实际上，我觉得这两个数学性质都蛮好想的，个人感觉不用看证明。

另外，编程时注意以下几点：

1）一个AP数的质因子数不会超过10，不然大于数据范围

2）用long long型变量存储答案，不然会爆

3）指数递减

代码：

 #include<cmath>

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 long long n,ap,fap;//ap是要输出的答案，fap是答案的质因子数

 int mm[]={,,,,,,,,,};//可能的质因子

 void dfs(long long num,int fnum,int i,int j){

     if(fap<fnum||(fap==fnum&&ap>num)){//更改输出答案的条件

         fap=fnum;

         ap=num;

     }

     int t=;

     while(t<=j&&num*mm[i]<=n){//直接判断

         num*=mm[i];

         dfs(num,fnum*(t+),i+,t);

         t++;

     }

     return;

 }

 int main(){

     while(scanf("%d",&n)!=EOF){//多组数据

         ap=fap=;//赋初值，不然会错的很惨

         dfs(,,,);

         cout<<ap<<endl;

     }

     return ;

 }

呐呐，就是这样了哦，新人博客，多多支持一下吧，嘻嘻~~~

巴特西

P1820 【寻找AP数】

最新文章

热门文章