ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203227 | #571. 斐波那契 | hegm | 100 | 795ms | 16788kb | C++11 | 941b | 2024-02-21 08:19:17 | 2024-02-21 12:09:52 |
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define ull unsigned long long
#define make make_pair
#define N 2000006
#define mod 1000000007
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,ans[N],f[N];
int add(int a,int b){return ((1ll*a+b)%mod+mod)%mod;}
int mul(int a,int b){return (1ll*a*b)%mod;}
signed main()
{
n=read();m=read();int p=min(n,m);
f[2]=1;f[1]=1;
for(int i=3;i<=p;i++)f[i]=add(f[i-1],f[i-2]);
for(int i=1;i<=p;i++)
{
int ans1=0,ans2=0;
for(int j=i;j<=n;j+=i)ans1++;
for(int j=i;j<=m;j+=i)ans2++;
ans[i]=mul(ans1,ans2);
}
for(int i=p-1;i>=1;i--)
{
for(int j=i*2;j<=p;j+=i)
ans[i]=add(ans[i],-1*ans[j]);
}
int sum=0;
for(int i=1;i<=p;i++)sum=add(sum,mul(ans[i],f[i]));
cout<<sum<<"\n";
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1168kb
input:
10 10
output:
251
result:
ok single line: '251'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1176kb
input:
1000 981
output:
201652910
result:
ok single line: '201652910'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1176kb
input:
906 1000
output:
524439478
result:
ok single line: '524439478'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1176kb
input:
1000 1000
output:
542559755
result:
ok single line: '542559755'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1172kb
input:
507 507
output:
112783388
result:
ok single line: '112783388'
Test #6:
score: 10
Accepted
time: 6ms
memory: 1944kb
input:
100000 100000
output:
766972956
result:
ok single line: '766972956'
Test #7:
score: 10
Accepted
time: 157ms
memory: 8976kb
input:
1000000 1000000
output:
272430913
result:
ok single line: '272430913'
Test #8:
score: 10
Accepted
time: 149ms
memory: 8244kb
input:
2000000 905234
output:
57001167
result:
ok single line: '57001167'
Test #9:
score: 10
Accepted
time: 150ms
memory: 8600kb
input:
951250 2000000
output:
390388595
result:
ok single line: '390388595'
Test #10:
score: 10
Accepted
time: 333ms
memory: 16788kb
input:
2000000 2000000
output:
46360093
result:
ok single line: '46360093'