| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20011 |
2016-02-25T08:26:13 Z |
Namnamseo |
팔찌 (kriii4_V) |
C++14 |
|
488 ms |
17684 KB |
#include<cstdio>
#include<bitset>
int M=int(1e9)+7;
int pow(int x,int y){
if(y==0)return 1;
if(y==1)return x;
long long o=pow(x,y/2);
if(y%2==0)return o*o%M;
else return o*o%M*x%M;
}
int ans [1000010];
int phi [1000010];
int kpow[1000010];
int rev [1000010];
bool sieve[1000010];
int n,k;
int modInverse(int a, int m=M)
{
int m0 = m, t, q;
int x0 = 0, x1 = 1;
if (m == 1)
return 0;
while (a > 1)
{
q = a / m;
t = m;
m = a % m, a = t;
t = x0;
x0 =x1-q*x0;
x1 = t;
}
// Make x1 positive
if (x1 < 0)
x1 += m0;
return x1;
}
int main(){
scanf("%d%d",&n,&k);
int i,j;
kpow[0]=1; kpow[1]=k; phi[1]=1; ans[1]=k;
for(i=2; i<=n; ++i){
kpow[i]=kpow[i-1]*((long long)k)%M;
ans[i]=kpow[i];
if(!sieve[i]){
for(j=i; j<=n; j+=i){
sieve[j]=true;
if(phi[j]==0) phi[j]=j;
phi[j] /= i;
phi[j] *= i-1;
}
}
}
for(i=2; i<=n; ++i){
long long cp=phi[i];
int cnt=1;
for(j=i; j<=n; ++cnt, j+=i){
ans[j] += cp * kpow[cnt] % M;
ans[j] %= M;
}
}
int tmp, half=pow(2, M-2), sumans = 2;
for(i=1; i<=n; ++i){
tmp = ((long long)ans[i]) * modInverse(i) % M;
sumans += tmp;
sumans %= M;
if(i&1){
sumans += kpow[(i+1)>>1];
sumans %= M;
} else {
sumans += ((long long)(k+1))*half%M*kpow[i>>1]%M;
sumans %= M;
}
}
printf("%d\n",int(sumans*((long long)half)%M));
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 4 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 5 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 6 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 7 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 8 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 9 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 10 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 11 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 12 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 13 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 14 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 15 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 16 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 17 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 18 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 19 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 20 |
Correct |
0 ms |
17684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 3 |
Correct |
0 ms |
17684 KB |
Output is correct |
| 4 |
Correct |
22 ms |
17684 KB |
Output is correct |
| 5 |
Correct |
289 ms |
17684 KB |
Output is correct |
| 6 |
Correct |
363 ms |
17684 KB |
Output is correct |
| 7 |
Correct |
277 ms |
17684 KB |
Output is correct |
| 8 |
Correct |
343 ms |
17684 KB |
Output is correct |
| 9 |
Correct |
393 ms |
17684 KB |
Output is correct |
| 10 |
Correct |
466 ms |
17684 KB |
Output is correct |
| 11 |
Correct |
390 ms |
17684 KB |
Output is correct |
| 12 |
Correct |
445 ms |
17684 KB |
Output is correct |
| 13 |
Correct |
262 ms |
17684 KB |
Output is correct |
| 14 |
Correct |
433 ms |
17684 KB |
Output is correct |
| 15 |
Correct |
244 ms |
17684 KB |
Output is correct |
| 16 |
Correct |
292 ms |
17684 KB |
Output is correct |
| 17 |
Correct |
481 ms |
17684 KB |
Output is correct |
| 18 |
Correct |
280 ms |
17684 KB |
Output is correct |
| 19 |
Correct |
348 ms |
17684 KB |
Output is correct |
| 20 |
Correct |
488 ms |
17684 KB |
Output is correct |
