oj.uz

답안 #20011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20011 2016-02-25T08:26:13 Z Namnamseo 팔찌 (kriii4_V) C++14
100 / 100
 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;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 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

Subtask #2
94.0 / 94.0

# 결과 실행 시간 메모리 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