Submission #20011

#	Time	Username	Problem	Language	Result	Execution time	Memory
20011		Namnamseo	팔찌 (kriii4_V)	C++14	100 / 100	488 ms	17684 KiB

V

#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;
}

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