Submission #20113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20113	2016-02-25T16:15:08 Z	gs14004	팔찌 (kriii4_V)	C++14	100 / 100	567 ms	25160 KB

V

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
    lint ret = 1, piv = x % mod;
    while(p){
        if(p&1) ret *= piv;
        piv *= piv;
        ret %= mod;
        piv %= mod;
        p >>= 1;
    }
    return ret;
}

int low[1000005], phi[1000005];
lint kpow[1000005], inv[1000005];
int n, k;

int main(){
	cin >> n >> k;
	phi[1] = 1;
	for(int i=2; i<=n; i++){
		for(int j=i; j<=n; j+=i){
			if(!low[j]) low[j] = i;
		}
		phi[i] = i;
		for(int j=i; j!=1; ){
			int p = low[j];
			while(j % p == 0){
				j /= p;
			}
			phi[i] = (1ll * phi[i] * (p-1)) / p;
		}
	}
	kpow[0] = 1;
	for(int i=1; i<=n; i++){
		kpow[i] = kpow[i-1] * k % mod;
		inv[i] = ipow(i, mod-2);
	}
	lint ret = 2;
	for(int i=1; i<=n; i++){
		for(int j=i; j<=n; j+=i){
			lint tmp = kpow[i] * phi[j/i] % mod;
			tmp *= inv[j];
			tmp %= mod;
			ret += tmp;
		}
	}
	for(int i=1; i<=n; i++){
		if(i%2 == 0) ret += (1ll * (k+1) * kpow[i/2] % mod) * ((mod + 1) / 2) % mod;
		else ret += kpow[i/2+1];
		ret %= mod;
	}
	ret *= (mod + 1) / 2;
	ret %= mod;
	cout << ret;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	25160 KB	Output is correct
2	Correct	0 ms	25160 KB	Output is correct
3	Correct	0 ms	25160 KB	Output is correct
4	Correct	0 ms	25160 KB	Output is correct
5	Correct	0 ms	25160 KB	Output is correct
6	Correct	1 ms	25160 KB	Output is correct
7	Correct	0 ms	25160 KB	Output is correct
8	Correct	0 ms	25160 KB	Output is correct
9	Correct	0 ms	25160 KB	Output is correct
10	Correct	0 ms	25160 KB	Output is correct
11	Correct	0 ms	25160 KB	Output is correct
12	Correct	0 ms	25160 KB	Output is correct
13	Correct	0 ms	25160 KB	Output is correct
14	Correct	0 ms	25160 KB	Output is correct
15	Correct	0 ms	25160 KB	Output is correct
16	Correct	0 ms	25160 KB	Output is correct
17	Correct	0 ms	25160 KB	Output is correct
18	Correct	0 ms	25160 KB	Output is correct
19	Correct	0 ms	25160 KB	Output is correct
20	Correct	0 ms	25160 KB	Output is correct

Subtask #2

94.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	25160 KB	Output is correct
2	Correct	0 ms	25160 KB	Output is correct
3	Correct	0 ms	25160 KB	Output is correct
4	Correct	29 ms	25160 KB	Output is correct
5	Correct	348 ms	25160 KB	Output is correct
6	Correct	427 ms	25160 KB	Output is correct
7	Correct	326 ms	25160 KB	Output is correct
8	Correct	407 ms	25160 KB	Output is correct
9	Correct	461 ms	25160 KB	Output is correct
10	Correct	546 ms	25160 KB	Output is correct
11	Correct	468 ms	25160 KB	Output is correct
12	Correct	527 ms	25160 KB	Output is correct
13	Correct	313 ms	25160 KB	Output is correct
14	Correct	505 ms	25160 KB	Output is correct
15	Correct	294 ms	25160 KB	Output is correct
16	Correct	347 ms	25160 KB	Output is correct
17	Correct	561 ms	25160 KB	Output is correct
18	Correct	326 ms	25160 KB	Output is correct
19	Correct	399 ms	25160 KB	Output is correct
20	Correct	567 ms	25160 KB	Output is correct