这道题,大家一定要注意:
要对2^31取模 ! ( 本蒟蒻开始没注意到这一点,WA了 )
(不过大家在试样例的时候,试试47,出不了结果,就说明你没模2^31)
总体来说,这道题考查的知识点就两个:
① 斐波那契递推公式 ( a[n]=a[n-1]+a[n-2] )
② 分解质因数 ( 不要跟因式分解混淆了 )
首先,让我们来看一看斐波那契递推公式:
const long long x=pow(2,31);//2^31
a[1]=1;
a[2]=1;
for(i=3;i<=n;i++)
a[i]=(a[i-1]+a[i-2])%x;//long long a[49],i;
很简单吧!(只要记得公式就好办了)
其次,让我们看一看分解质因数:
for(i=2;a[n]>1;i++){
if(a[n]%i==0){//i是a[n]的因数
a[n]/=i;//记得要除
printf("%lld",i);
break;//先处理没有乘号的地方
}
}
for(j=i;a[n]>1;j++){
if(a[n]%j==0){//j是a[n]的因数
printf("*%lld",j);
a[n]/=j;//这里也是
while(a[n]%j==0){
printf("*%lld",j);
a[n]/=j;//还有这里
}
if(a[n]==1)//特判
return 0;//若a[n]为0则分解完毕,退出
}
}
只是要注意等号后面第一个不能输出乘号,得重复走两遍
贴出完整代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//自定义
const long long x=pow(2,31);//pow(a,b)为计算a^b
ll i,n,j,a[51];//ll是自己定义的
int main(){
scanf("%lld",&n);
a[1]=1;
a[2]=1;
for(i=3;i<=n;i++)
a[i]=(a[i-1]+a[i-2])%x;//递推走起
printf("%lld=",a[n]);
for(i=2;a[n]>1;i++){
if(a[n]%i==0){
a[n]/=i;
printf("%lld",i);
break;
}
}
for(j=i;a[n]>1;j++){
if(a[n]%j==0){
printf("*%lld",j);
a[n]/=j;
while(a[n]%j==0){
printf("*%lld",j);
a[n]/=j;
}
if(a[n]==1)
return 0;
}
}//分解质因数
if(n==1||n==2)
printf("1");//不特判n=1和n=2时就无法输出
return 0;
}
洛谷加油!OI冲鸭!