NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #203223 | #571. 斐波那契 | snow_trace | 100 | 454ms | 32448kb | C++11 | 508b | 2024-02-21 07:52:28 | 2024-02-21 12:09:38 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000000007;
int n,m;int ans = 0;int f[20000005],cnt[2000005];
signed main(){
cin >> n >> m;
f[1] = 1,f[2] = 1;
for(int i =3;i<=2000000;i++)f[i] = (f[i-1]+f[i-2])%mod;
for(int i = 1;i<=n;i++){
cnt[i] = (n/i)*(m/i);
}for(int i = n;i>=1;i--){
for(int j = 2*i;j<=n;j+=i)cnt[i]-=cnt[j];
}for(int i = 1;i<=n;i++)ans+=cnt[i]%mod*f[i]%mod,ans%=mod;
//cout << ans << endl;
cout<< ans << endl;
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 12ms
memory: 16824kb
input:
10 10
output:
251
result:
ok single line: '251'
Test #2:
score: 10
Accepted
time: 10ms
memory: 16832kb
input:
1000 981
output:
201652910
result:
ok single line: '201652910'
Test #3:
score: 10
Accepted
time: 8ms
memory: 16832kb
input:
906 1000
output:
524439478
result:
ok single line: '524439478'
Test #4:
score: 10
Accepted
time: 15ms
memory: 16836kb
input:
1000 1000
output:
542559755
result:
ok single line: '542559755'
Test #5:
score: 10
Accepted
time: 11ms
memory: 16832kb
input:
507 507
output:
112783388
result:
ok single line: '112783388'
Test #6:
score: 10
Accepted
time: 16ms
memory: 17608kb
input:
100000 100000
output:
766972956
result:
ok single line: '766972956'
Test #7:
score: 10
Accepted
time: 59ms
memory: 24636kb
input:
1000000 1000000
output:
272430913
result:
ok single line: '272430913'
Test #8:
score: 10
Accepted
time: 137ms
memory: 32444kb
input:
2000000 905234
output:
57001167
result:
ok single line: '57001167'
Test #9:
score: 10
Accepted
time: 50ms
memory: 24256kb
input:
951250 2000000
output:
390388595
result:
ok single line: '390388595'
Test #10:
score: 10
Accepted
time: 136ms
memory: 32448kb
input:
2000000 2000000
output:
46360093
result:
ok single line: '46360093'
