oj.uz

답안 #19752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19752 2016-02-25T05:16:39 Z Qwaz 팔찌 (kriii4_V) C++
100 / 100
 552 ms 15032 KB 
#include <iostream>
#include <vector>
using namespace std;

typedef long long int ll;

const ll mod = 1000000007LL;

// computes a * b mod n
inline ll times_mod(ll a, ll b, ll n)
{
	return a * b % n;
}

// solves a*x + b*y = d = gcd(a, b)
// if d == 1, x is a modular inverse of a mod b
void extended_gcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if(a < 0) {extended_gcd(-a, b, d, x, y); x *= -1; return;}
    if(b < 0) {extended_gcd(a, -b, d, x, y); y *= -1; return;}
	x = 0, y = 1;
	ll lx = 1, ly = 0, frac, tmp;
	while(b)
	{
		frac = a / b; 
		tmp = a; a = b; b = tmp % b;
		tmp = x; x = lx - frac * x; lx = tmp;
		tmp = y; y = ly - frac * y; ly = tmp;
	}
	x = lx; y = ly; d = a;
}

// reduces ? == x (mod a) && ? == y (mod b) to ? == z (mod c)
// returns true on succes
// assumes that a / gcd(a, b) * b will never overflow
bool chinese(ll x, ll a, ll y, ll b, ll &z, ll &c)
{
	ll s, t, d;
	extended_gcd(a, b, d, s, t);
	if(x % d != y % d) return false;
	c = a / d * b; 
	z = times_mod(times_mod(a / d, y, c), s, c);
	z = (z + times_mod(times_mod(b / d, x, c), t, c)) % c;
	return true;
}

// calculates x^-1 mod a
ll inv_mod(ll x, ll a)
{
    ll res, y, d;
    extended_gcd(x, a, d, res, y);
    return ((res % a) + a) % a;
}

// computes a ^ b mod n
ll pow_mod(ll a, ll b, ll n)
{
    if(b < 0) return inv_mod(pow_mod(a, -b, n), n);
	ll t, result = 1;
	for(t = a % n; b; t = times_mod(t, t, n), b >>= 1)
		if(b & 1) result = times_mod(result, t, n);

	return result;
}

ll gcd(ll a, ll b)
{
	if(!b) return a;
	else return gcd(b, a % b);
}

int n, k;
bool is_prime[1048576] = {false};
int euler_phi[1048576];
int pow_k[1048576];
int ans[1048576] = {0};

int main() {
	cin >> n >> k;

	// compute euler_phi
	for (int i = 1; i <= n; i++) {
		is_prime[i] = (i >= 2);
		euler_phi[i] = i;
	}
	for (int i = 2; i <= n; i++)
		if (is_prime[i])
			for (int j = i; j <= n; j += i) {
				is_prime[j] = (j == i);
				euler_phi[j] = (euler_phi[j] / i) * (i - 1);
			}

	// compute pow_k
	pow_k[0] = 1;
	for (int i = 1; i <= n; i++)
		pow_k[i] = times_mod(pow_k[i - 1], k, mod);

	// rotation
	for (int d = 1; d <= n; d++)
		for (int x = d; x <= n; x += d) {
			ans[x] = (ans[x] + times_mod(euler_phi[x / d], pow_k[d], mod)) % mod;
		}

	// cout << "hi" << endl;

	// flip
	for (int x = 1; x <= n; x++) {
		if (x % 2 == 0) {
			ans[x] = (ans[x] + times_mod(x / 2, pow_k[x / 2 + 1], mod)) % mod;
			ans[x] = (ans[x] + times_mod(x / 2, pow_k[x / 2], mod)) % mod;
		}
		else {
			ans[x] = (ans[x] + times_mod(x, pow_k[(x + 1) / 2], mod)) % mod;
		}

		// modding out
	}

	// cout << "hi" << endl;

	for (int x = 1; x <= n; x++)
		ans[x] = times_mod(ans[x], inv_mod(2 * x, mod), mod);

	// cout << "hi" << endl;

	/*
	for (int x = 1; x <= n; x++)
		cout << ans[x] << " ";
	cout << endl;
	*/
	int res = 1;
	for (int i = 1; i <= n; i++)
		res = (res + ans[i]) % mod;
	cout << res << endl;

	return 0;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 15032 KB Output is correct
2 Correct 0 ms 15032 KB Output is correct
3 Correct 0 ms 15032 KB Output is correct
4 Correct 0 ms 15032 KB Output is correct
5 Correct 0 ms 15032 KB Output is correct
6 Correct 0 ms 15032 KB Output is correct
7 Correct 0 ms 15032 KB Output is correct
8 Correct 0 ms 15032 KB Output is correct
9 Correct 0 ms 15032 KB Output is correct
10 Correct 0 ms 15032 KB Output is correct
11 Correct 0 ms 15032 KB Output is correct
12 Correct 0 ms 15032 KB Output is correct
13 Correct 0 ms 15032 KB Output is correct
14 Correct 0 ms 15032 KB Output is correct
15 Correct 0 ms 15032 KB Output is correct
16 Correct 0 ms 15032 KB Output is correct
17 Correct 0 ms 15032 KB Output is correct
18 Correct 0 ms 15032 KB Output is correct
19 Correct 0 ms 15032 KB Output is correct
20 Correct 0 ms 15032 KB Output is correct

Subtask #2
94.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 15032 KB Output is correct
2 Correct 0 ms 15032 KB Output is correct
3 Correct 0 ms 15032 KB Output is correct
4 Correct 26 ms 15032 KB Output is correct
5 Correct 324 ms 15032 KB Output is correct
6 Correct 404 ms 15032 KB Output is correct
7 Correct 310 ms 15032 KB Output is correct
8 Correct 388 ms 15032 KB Output is correct
9 Correct 444 ms 15032 KB Output is correct
10 Correct 520 ms 15032 KB Output is correct
11 Correct 449 ms 15032 KB Output is correct
12 Correct 507 ms 15032 KB Output is correct
13 Correct 298 ms 15032 KB Output is correct
14 Correct 484 ms 15032 KB Output is correct
15 Correct 268 ms 15032 KB Output is correct
16 Correct 335 ms 15032 KB Output is correct
17 Correct 540 ms 15032 KB Output is correct
18 Correct 318 ms 15032 KB Output is correct
19 Correct 384 ms 15032 KB Output is correct
20 Correct 552 ms 15032 KB Output is correct