Submission #19915

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19915	2016-02-25T07:02:54 Z	cki86201	팔찌 (kriii4_V)	C++14	6 / 100	1000 ms	17348 KB

V

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

const ll MOD = 1e9 + 7;

ll pw(ll x, ll y){
	ll res = 1;
	while(y){
		if(y & 1)res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}

ll pwk[1000010];
int phi[1000010];
int isp[1000010];

int main(){
	int N, K;
	scanf("%d%d", &N, &K);
	pwk[0] = 1;
	for(int i=1;i<1000010;i++)pwk[i] = K * pwk[i-1] % MOD;
	phi[1] = 1;
	for(int i=2;i<1000010;i++)phi[i] = i, isp[i] = 1;
	for(int i=2;i<1000010;i++){
		if(isp[i]){
			phi[i] = i-1;
			for(int j=i+i;j<1000010;j+=i){
				isp[j] = 0;
				phi[j] /= i;
				phi[j] *= (i-1);
			}
		}
	}
	ll ans = 1;
	ll p2 = pw(2, MOD-2);
	ll p4 = pw(4, MOD-2);
	for(int i=1;i<=N;i++){
		ll sum = 0;
		for(int j=1;j*j<=i;j++){
			if(i % j != 0)continue;
			sum += phi[j] * pwk[i/j];
			sum %= MOD;
			if(j*j != i){
				sum += phi[i/j] * pwk[j];
				sum %= MOD;
			}
		}
		//printf("%d %lld\n", i, sum);
		ans += sum * pw(2*i, MOD-2);
		if(i & 1)ans += p2 * pwk[(i+1)/2];
		else ans += p4 * (K+1) % MOD * pwk[i/2];
		ans %= MOD;
	}
	printf("%lld", ans);
	return 0;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	17348 KB	Output is correct
2	Correct	47 ms	17348 KB	Output is correct
3	Correct	47 ms	17348 KB	Output is correct
4	Correct	40 ms	17348 KB	Output is correct
5	Correct	47 ms	17348 KB	Output is correct
6	Correct	50 ms	17348 KB	Output is correct
7	Correct	43 ms	17348 KB	Output is correct
8	Correct	50 ms	17348 KB	Output is correct
9	Correct	46 ms	17348 KB	Output is correct
10	Correct	42 ms	17348 KB	Output is correct
11	Correct	47 ms	17348 KB	Output is correct
12	Correct	47 ms	17348 KB	Output is correct
13	Correct	50 ms	17348 KB	Output is correct
14	Correct	50 ms	17348 KB	Output is correct
15	Correct	50 ms	17348 KB	Output is correct
16	Correct	46 ms	17348 KB	Output is correct
17	Correct	49 ms	17348 KB	Output is correct
18	Correct	46 ms	17348 KB	Output is correct
19	Correct	50 ms	17348 KB	Output is correct
20	Correct	50 ms	17348 KB	Output is correct

Subtask #2

0.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	17348 KB	Output is correct
2	Correct	47 ms	17348 KB	Output is correct
3	Correct	48 ms	17348 KB	Output is correct
4	Correct	118 ms	17348 KB	Output is correct
5	Execution timed out	1000 ms	17344 KB	Program timed out
6	Halted	0 ms	0 KB	-