Submission #19923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19923	2016-02-25T07:17:12 Z	myungwoo	팔찌 (kriii4_V)	C++14	0 / 100	0 ms	32364 KB

V

#include<stdio.h>
#include<memory.h>
#define mod 1000000007
#define inv(a) exp(a,mod-2)

typedef long long lld;

lld exp(lld a, lld b){
	if(b==0)return 1;
	lld k=exp(a, b/2);
	k=(k*k)%mod;
	if(b%2)k=(k*a)%mod;
	return k;
}

lld fac[1001001], rfac[1001001];

void init(){
	lld i;
	fac[0]=rfac[0]=1;
	for(i=1; i<=1000000; i++){
		fac[i]=(fac[i-1]*i)%mod;
		rfac[i]=inv(fac[i]);
	}
}

lld comb(lld a, lld b){
	return fac[a]*rfac[b]%mod*rfac[a-b]%mod;
}

lld n, k;
lld all[1001001];
lld all2[1001001];
lld sum, lr, dap;

int main(){
	lld i, j;
//	init();
	scanf("%lld%lld", &n, &k);
	all[0]=1;
	for(i=1; i<=n; i++){
		all[i]%=mod;
		if(all[i]<0)all[i]+=mod;
		all[i]+=exp(k,i), all[i]%=mod;
		for(j=2*i; j<=n; j+=i)all[j]-=all[i];
	}
	for(i=1; i<=n; i++){
		sum += all[i]*(n/i)%mod * inv(i);
		sum %= mod;
	}

	all2[0]=1;
	for(i=1; i<=n; i++){
		all2[i]%=mod;
		if(all2[i]<0)all2[i]+=mod;
		all2[i]+=exp(k,i/2+1), all2[i]%=mod;
		for(j=2*i; j<=n; j+=i)all2[j]-=all2[i];
	}
	all2[4]=2;
	for(i=1; i<=n; i++){
		lld im = all2[i]*(n/i)%mod;
		if(i%2 == 0)im *= inv(2);
//		else im *= inv(i);
		lr += im;
		lr %= mod;
	}
//	if(n>=2)lr += all[2]*inv(2), lr%=mod;

	dap = (sum+lr)*inv(2)%mod;
	dap = (dap+1)%mod;
	printf("%lld", dap);
	return 0;
}

Subtask #1

0.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	32364 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Halted	0 ms	0 KB	-