首页 > 代码库 > E - 追求
E - 追求
经历了那晚的竹林深处相识后静竹对数学念念不忘，产生了好感！为了追求数学，她想到了一招，要想搞定女友，搞定闺中密友。于是，她秘密与数学的好友斐波那契见面了。学数学的真是不一样，斐波那契的出现前提也是需要解决一道题目，你能帮助静竹同学吗？
斐波那契发明了一种数，他的规律就是F(n)=F(n-1)+F(n-2),其中F(0)=K，F(1)=Q
求第n项的值已经很简单了，现在的问题是需要你求出第n项的值对应的数有多少个不大于n的正整数因子
Input
有多组测试数据
每组测试数据中，第一行输入三个整数，K,Q,T(0<=K, Q, T<1000,)
接下来有T行，每行输入一个整数n(0<=n<1000)
处理到文件结束
Output
按照样例输出要求输出，首先Case k：,k表示第k组测试数据
接下来输出T行，每行输出一个整数代表当前行输入的数n的F(n)值不大于n的正整数因子数目。
Sample Input1 1 2
2
3Sample OutputCase 1:
2
2
肯定不能暴力的，为什么，因为第1000个斐波那契数会爆了long long 然后这个题就挂掉了，每次新求一个斐波那契数，然后再暴力一下就OK了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[1111];
int f[1111];
int k,q,t;
int n;
int sum;
int main()
{
int cnt=1;
while(~scanf("%d%d%d",&k,&q,&t))
{
printf("Case %d:\n",cnt);
cnt++;
while(t--)
{
scanf("%d",&n);
if(n<2)
{
if(n==0)
printf("0\n");
else
printf("1\n");
}
else
{
sum=0;
memset(f,0,sizeof(f));
f[0]=k;
f[1]=q;
for(int i=1; i<=n; i++)
{
for(int j=2; j<=n; j++)
{
f[j]=(f[j-1]%i+f[j-2]%i)%i;
}
if(f[n]==0)
sum++;
}
printf("%d\n",sum);
}
}
}
return 0;
}
E - 追求
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。