답안 #633656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633656 2022-08-23T01:07:56 Z lkh3happy 팔찌 (kriii4_V) C++14
100 / 100
465 ms 23736 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<=max(n, 4LL);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;
    printf("%lld\n", (ans*mi[4]+1)%mod);
    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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 300 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 296 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 27 ms 1464 KB Output is correct
5 Correct 289 ms 14808 KB Output is correct
6 Correct 347 ms 17904 KB Output is correct
7 Correct 282 ms 14108 KB Output is correct
8 Correct 336 ms 17240 KB Output is correct
9 Correct 377 ms 19548 KB Output is correct
10 Correct 449 ms 22720 KB Output is correct
11 Correct 384 ms 19624 KB Output is correct
12 Correct 448 ms 22032 KB Output is correct
13 Correct 257 ms 13368 KB Output is correct
14 Correct 415 ms 21216 KB Output is correct
15 Correct 241 ms 12644 KB Output is correct
16 Correct 297 ms 15040 KB Output is correct
17 Correct 459 ms 23552 KB Output is correct
18 Correct 281 ms 14184 KB Output is correct
19 Correct 347 ms 17212 KB Output is correct
20 Correct 465 ms 23736 KB Output is correct