Submission #633656

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
633656	2022-08-23 01:07:56	lkh3happy	팔찌 (kriii4_V)	C++14	100 / 100	465 ms	23736 KiB

V

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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: 6 / 6
• Subtask 2: 94 / 94