oj.uz

Submission #633653

# Submission time Handle Problem Language Result Execution time Memory
633653 2022-08-23T01:02:43 Z lkh3happy 팔찌 (kriii4_V) C++14
94 / 100
 457 ms 23840 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;
    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);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 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 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 25 ms 1492 KB Output is correct
5 Correct 290 ms 14796 KB Output is correct
6 Correct 356 ms 18028 KB Output is correct
7 Correct 276 ms 14096 KB Output is correct
8 Correct 337 ms 17240 KB Output is correct
9 Correct 386 ms 19608 KB Output is correct
10 Correct 441 ms 22608 KB Output is correct
11 Correct 378 ms 19716 KB Output is correct
12 Correct 425 ms 22004 KB Output is correct
13 Correct 259 ms 13372 KB Output is correct
14 Correct 416 ms 21180 KB Output is correct
15 Correct 244 ms 12640 KB Output is correct
16 Correct 291 ms 15008 KB Output is correct
17 Correct 453 ms 23740 KB Output is correct
18 Correct 273 ms 14232 KB Output is correct
19 Correct 336 ms 17300 KB Output is correct
20 Correct 457 ms 23840 KB Output is correct