Submission #19968

#	Time	Username	Problem	Language	Result	Execution time	Memory
19968		Namnamseo	팔찌 (kriii4_V)	C++14	6 / 100	1000 ms	24644 KiB

V

#include<cstdio>
#include<bitset>
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];
std::bitset<1000010> sieve;
int n,k;
int main(){
    scanf("%d%d",&n,&k);
    int i,j;
    kpow[0]=1; kpow[1]=k; phi[1]=1;
    for(i=2; i<=n; ++i){
        kpow[i]=kpow[i-1]*k%M;
        if(sieve[i]) continue;
        // i is prime.
        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=1; 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 = 1;
    for(i=1; i<=n; ++i){
        tmp = ans[i] * half % M * pow(i,M-2) % M;
        sumans += tmp;
        sumans %= M;
        if(i&1){
            sumans += pow(k,(i+1)/2)*half%M;
            sumans %= M;
        } else {
            sumans += (k+1)*half%M*half%M*pow(k,i/2)%M;
            sumans %= M;
        }
    }
    printf("%lld\n",sumans);
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 94