Submission #633656

#	Time	Username	Problem	Language	Result	Execution time	Memory
633656		lkh3happy	팔찌 (kriii4_V)	C++14	100 / 100	465 ms	23736 KiB

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<=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 (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