Submission #633654

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
633654	2022-08-23T01:04:18 Z	lkh3happy	팔찌 (kriii4_V)	C++14	94 / 100	469 ms	23752 KB

V

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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