| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19920 |
2016-02-25T07:16:30 Z |
cki86201 |
팔찌 (kriii4_V) |
C++14 |
|
384 ms |
25160 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
const ll MOD = 1e9 + 7;
ll pw(ll x, ll y){
ll res = 1;
while(y){
if(y & 1)res = res * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return res;
}
ll pwk[1000010];
int phi[1000010];
int isp[1000010];
ll sum[1000010];
int main(){
int N, K;
scanf("%d%d", &N, &K);
//N = K = 1000000;
pwk[0] = 1;
for(int i=1;i<1000010;i++)pwk[i] = K * pwk[i-1] % MOD;
phi[1] = 1;
for(int i=2;i<1000010;i++)phi[i] = i, isp[i] = 1;
for(int i=2;i<1000010;i++){
if(isp[i]){
phi[i] = i-1;
for(int j=i+i;j<1000010;j+=i){
isp[j] = 0;
phi[j] /= i;
phi[j] *= (i-1);
}
}
}
ll ans = 1;
ll p2 = pw(2, MOD-2);
ll p4 = pw(4, MOD-2);
for(int i=1;i<=N;i++){
for(int j=i,t=1;j<=N;j+=i,t++){
sum[j] += phi[i] * pwk[t];
sum[j] %= MOD;
}
}
for(int i=1;i<=N;i++){
//printf("%d %lld\n", i, sum);
ans += sum[i] * pw(2*i, MOD-2);
if(i & 1)ans += p2 * pwk[(i+1)/2];
else ans += p4 * (K+1) % MOD * pwk[i/2];
ans %= MOD;
}
printf("%lld", ans);
//printf("\n%d", clock());
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
25160 KB |
Output is correct |
| 2 |
Correct |
46 ms |
25160 KB |
Output is correct |
| 3 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 4 |
Correct |
42 ms |
25160 KB |
Output is correct |
| 5 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 6 |
Correct |
46 ms |
25160 KB |
Output is correct |
| 7 |
Correct |
46 ms |
25160 KB |
Output is correct |
| 8 |
Correct |
46 ms |
25160 KB |
Output is correct |
| 9 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 10 |
Correct |
42 ms |
25160 KB |
Output is correct |
| 11 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 12 |
Correct |
46 ms |
25160 KB |
Output is correct |
| 13 |
Correct |
51 ms |
25160 KB |
Output is correct |
| 14 |
Correct |
49 ms |
25160 KB |
Output is correct |
| 15 |
Correct |
45 ms |
25160 KB |
Output is correct |
| 16 |
Correct |
49 ms |
25160 KB |
Output is correct |
| 17 |
Correct |
49 ms |
25160 KB |
Output is correct |
| 18 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 19 |
Correct |
49 ms |
25160 KB |
Output is correct |
| 20 |
Correct |
46 ms |
25160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 2 |
Correct |
50 ms |
25160 KB |
Output is correct |
| 3 |
Correct |
46 ms |
25160 KB |
Output is correct |
| 4 |
Correct |
59 ms |
25160 KB |
Output is correct |
| 5 |
Correct |
250 ms |
25160 KB |
Output is correct |
| 6 |
Correct |
297 ms |
25160 KB |
Output is correct |
| 7 |
Correct |
246 ms |
25160 KB |
Output is correct |
| 8 |
Correct |
283 ms |
25160 KB |
Output is correct |
| 9 |
Correct |
319 ms |
25160 KB |
Output is correct |
| 10 |
Correct |
368 ms |
25160 KB |
Output is correct |
| 11 |
Correct |
321 ms |
25160 KB |
Output is correct |
| 12 |
Correct |
354 ms |
25160 KB |
Output is correct |
| 13 |
Correct |
226 ms |
25160 KB |
Output is correct |
| 14 |
Correct |
347 ms |
25160 KB |
Output is correct |
| 15 |
Correct |
215 ms |
25160 KB |
Output is correct |
| 16 |
Correct |
256 ms |
25160 KB |
Output is correct |
| 17 |
Correct |
382 ms |
25160 KB |
Output is correct |
| 18 |
Correct |
240 ms |
25160 KB |
Output is correct |
| 19 |
Correct |
288 ms |
25160 KB |
Output is correct |
| 20 |
Correct |
384 ms |
25160 KB |
Output is correct |
