oj.uz

Submission #20004

# Submission time Handle Problem Language Result Execution time Memory
20004 2016-02-25T08:22:02 Z Namnamseo 팔찌 (kriii4_V) C++14
6 / 100
 1000 ms 25496 KB 
#include<cstdio>
typedef long long ll;
ll M=int(1e9)+7;
ll pow(ll x,ll y){
    if(y==0)return 1;
    if(y==1)return x;
    ll o=pow(x,y/2);
    if(y%2==0)return o*o%M;
    else return o*o%M*x%M;
}
ll ans [1000010];
ll phi [1000010];
ll kpow[1000010];
bool sieve[1000010];
int n,k;
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]*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){
        for(j=i; j<=n; j+=i){
            ans[j] += phi[i] * kpow[j/i];
            ans[j] %= M;
        }
    }
    ll tmp, half=pow(2, M-2), sumans = 2;
    for(i=1; i<=n; ++i){
        tmp = ans[i] * pow(i,M-2);
        sumans += tmp;
        sumans %= M;
        if(i&1){
            sumans += kpow[(i+1)/2];
            sumans %= M;
        } else {
            sumans += (k+1)*half%M*kpow[i/2];
            sumans %= M;
        }
    }
    printf("%lld",sumans*half%M);
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25496 KB Output is correct
2 Correct 0 ms 25496 KB Output is correct
3 Correct 0 ms 25496 KB Output is correct
4 Correct 0 ms 25496 KB Output is correct
5 Correct 1 ms 25496 KB Output is correct
6 Correct 0 ms 25496 KB Output is correct
7 Correct 0 ms 25496 KB Output is correct
8 Correct 0 ms 25496 KB Output is correct
9 Correct 0 ms 25496 KB Output is correct
10 Correct 0 ms 25496 KB Output is correct
11 Correct 0 ms 25496 KB Output is correct
12 Correct 0 ms 25496 KB Output is correct
13 Correct 0 ms 25496 KB Output is correct
14 Correct 0 ms 25496 KB Output is correct
15 Correct 0 ms 25496 KB Output is correct
16 Correct 0 ms 25496 KB Output is correct
17 Correct 0 ms 25496 KB Output is correct
18 Correct 0 ms 25496 KB Output is correct
19 Correct 0 ms 25496 KB Output is correct
20 Correct 0 ms 25496 KB Output is correct

Subtask #2
0.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25496 KB Output is correct
2 Correct 0 ms 25496 KB Output is correct
3 Correct 0 ms 25496 KB Output is correct
4 Correct 74 ms 25496 KB Output is correct
5 Correct 880 ms 25496 KB Output is correct
6 Execution timed out 1000 ms 25496 KB Program timed out
7 Halted 0 ms 0 KB -