Submission #19915

#	Time	Username	Problem	Language	Result	Execution time	Memory
19915		cki86201	팔찌 (kriii4_V)	C++14	6 / 100	1000 ms	17348 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];

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 / 6
• Subtask 2: 0 / 94