UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203227#571. 斐波那契hegm100795ms16788kbC++11941b2024-02-21 08:19:172024-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'