oj.uz

답안 #633654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633654 2022-08-23T01:04:18 Z lkh3happy 팔찌 (kriii4_V) C++14
94 / 100
 469 ms 23752 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

long long mod=1e9+7, ep[1000001], mi[1000001]={1}, kp[1000001]={1};

long long po(long long x){
    long long sum=1, y=mod-2;
    for(;y;y>>=1, x=x*x%mod) if(y&1) sum=sum*x%mod;
    return sum;
}

int main(){
    long long n, k, ans=0;
    scanf("%lld%lld\n", &n, &k);
    for(int i=1;i<=n;i++) ep[i]=i;
    for(int i=2;i<=n;i++) if(ep[i]==i) for(int j=i;j<=n;j+=i) ep[j]=ep[j]/i*(i-1);
    for(int i=1;i<=n;i++) kp[i]=kp[i-1]*k%mod, ep[i]=(ep[i]*(mi[i]=po(i))+ep[i-1])%mod;
    for(int i=1;i<=n;i++) ans=(ans+(kp[i]*mi[i]%mod)*ep[n/i]*2+((i&1)?kp[i/2+1]*2:kp[i/2]+kp[i/2+1]))%mod;
    if(n^1) printf("%lld\n", (ans*mi[4]+1)%mod);
    else printf("%lld\n", k+1);
    return 0;
}

Compilation message

V.cpp: In function 'int main()':
V.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%lld%lld\n", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
94.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 25 ms 1516 KB Output is correct
5 Correct 297 ms 14756 KB Output is correct
6 Correct 356 ms 17960 KB Output is correct
7 Correct 279 ms 14028 KB Output is correct
8 Correct 335 ms 17240 KB Output is correct
9 Correct 395 ms 19504 KB Output is correct
10 Correct 437 ms 22704 KB Output is correct
11 Correct 394 ms 19572 KB Output is correct
12 Correct 427 ms 21964 KB Output is correct
13 Correct 265 ms 13260 KB Output is correct
14 Correct 412 ms 21168 KB Output is correct
15 Correct 254 ms 12644 KB Output is correct
16 Correct 287 ms 14904 KB Output is correct
17 Correct 469 ms 23588 KB Output is correct
18 Correct 271 ms 14156 KB Output is correct
19 Correct 344 ms 17208 KB Output is correct
20 Correct 462 ms 23752 KB Output is correct