답안 #474619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474619	2021-09-19T08:08:57 Z	egod1537	팔찌 (kriii4_V)	C++14	6 / 100	1000 ms	29760 KB

V

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

typedef pair<ll, ll> pi;
#define var first
#define cnt second

ll pwk[2000001], phi[1000001], low[1000001];
bitset<1000001> vit;
vector<ll> prime;

ll pow(ll x, ll p) {
	ll ret = 1, piv = x % mod;
	while (p) {
		if (p & 1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret;
}
ll revmod(ll x) { return pow(x, mod - 2) % mod; }	
vector<pi> getfactor(ll num) {
	vector<pi> ans;
	for (int i = 0; num > 1 && prime[i]*prime[i] <= num && i < prime.size(); i++) {
		ll now = prime[i];
		pi p = pi(now, 0);
		while (num % now == 0) {
			p.cnt++;
			num /= now;
		}
		if (p.cnt > 0) ans.push_back(p);
	}
	if (num > 1) ans.push_back(pi(num, 1));
	return ans;
}
ll dfs(int num, ll k, ll now, ll np, vector<pi>& arr, vector<vector<ll>>& psum) {
	if (num == arr.size()) return phi[np]*pwk[now];
	ll ans = 0;
	for (int i = 0; i <= arr[num].cnt; i++) 
		ans = (ans + dfs(num+1, k, now*psum[num][i], np*psum[num][arr[num].cnt-i], arr, psum))%mod;
	return ans;
}
ll r2;
ll func(ll n, ll k) {
	//if (n % 10000 == 0) cout << n << "\n";
	ll ans = 0;
	vector<pi> fact = getfactor(n);
	vector<vector<ll>> psum(fact.size());
	for (int i = 0; i < fact.size(); i++) {
		psum[i].resize(fact[i].cnt+1);
		psum[i][0] = 1;
		for (int j = 1; j <= fact[i].cnt; j++) 
			psum[i][j] = psum[i][j - 1] * fact[i].var;
	}
	ans = dfs(0, k, 1, 1, fact, psum);
	if (n % 2) ans = (ans + (n * pwk[n/2+1])%mod)%mod;
	else {
		ll pw = (pwk[n/2] + pwk[n/2+1]) % mod;
		ans = (ans + (((n * pw)%mod)*r2)%mod)%mod;
	}

	return (ans * revmod(2 * n)) % mod;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	for (int i = 2; i <= 1000000; i++) {
		if (!vit[i]) prime.push_back(i);
		else continue;
		for (int j = 2 * i; j <= 1000000; j += i) vit[j] = true;
	}

	ll n, k; 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;
		}
	}

	pwk[0] = 1;
	for (int i = 1; i <= 2000000; i++) pwk[i] = (pwk[i - 1] * k) % mod;
	r2 = revmod(2);

	ll ans = 1;
	for (int i = 1; i <= n; i++) ans = (ans + func(i, k)) % mod;
	cout << ans;

	return 0;
}

Compilation message

V.cpp: In function 'std::vector<std::pair<long long int, long long int> > getfactor(ll)':
V.cpp:34:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; num > 1 && prime[i]*prime[i] <= num && i < prime.size(); i++) {
      |                                                         ~~^~~~~~~~~~~~~~
V.cpp: In function 'll dfs(int, ll, ll, ll, std::vector<std::pair<long long int, long long int> >&, std::vector<std::vector<long long int> >&)':
V.cpp:47:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  if (num == arr.size()) return phi[np]*pwk[now];
      |      ~~~~^~~~~~~~~~~~~
V.cpp: In function 'll func(ll, ll)':
V.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < fact.size(); i++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	16840 KB	Output is correct
2	Correct	25 ms	16800 KB	Output is correct
3	Correct	25 ms	16820 KB	Output is correct
4	Correct	27 ms	16764 KB	Output is correct
5	Correct	27 ms	16840 KB	Output is correct
6	Correct	25 ms	16788 KB	Output is correct
7	Correct	25 ms	16804 KB	Output is correct
8	Correct	24 ms	16804 KB	Output is correct
9	Correct	24 ms	16828 KB	Output is correct
10	Correct	24 ms	16772 KB	Output is correct
11	Correct	24 ms	16816 KB	Output is correct
12	Correct	24 ms	16760 KB	Output is correct
13	Correct	24 ms	16760 KB	Output is correct
14	Correct	24 ms	16804 KB	Output is correct
15	Correct	24 ms	16840 KB	Output is correct
16	Correct	26 ms	16796 KB	Output is correct
17	Correct	24 ms	16776 KB	Output is correct
18	Correct	24 ms	16840 KB	Output is correct
19	Correct	25 ms	16748 KB	Output is correct
20	Correct	25 ms	16788 KB	Output is correct

Subtask #2

0 / 94.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	16840 KB	Output is correct
2	Correct	24 ms	16840 KB	Output is correct
3	Correct	25 ms	16872 KB	Output is correct
4	Correct	76 ms	17612 KB	Output is correct
5	Correct	741 ms	26432 KB	Output is correct
6	Correct	929 ms	28608 KB	Output is correct
7	Correct	690 ms	25916 KB	Output is correct
8	Correct	900 ms	28092 KB	Output is correct
9	Execution timed out	1012 ms	29760 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-