Submission #19920

#	Time	Username	Problem	Language	Result	Execution time	Memory
19920		cki86201	팔찌 (kriii4_V)	C++14	100 / 100	384 ms	25160 KiB

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];
ll sum[1000010];

int main(){
	int N, K;
	scanf("%d%d", &N, &K);
	//N = K = 1000000;
	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++){
		for(int j=i,t=1;j<=N;j+=i,t++){
			sum[j] += phi[i] * pwk[t];
			sum[j] %= MOD;
		}
	}
	for(int i=1;i<=N;i++){
		//printf("%d %lld\n", i, sum);
		ans += sum[i] * 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);
	//printf("\n%d", clock());
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94