Submission #19732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19732	2016-02-25T05:04:07 Z	Qwaz	팔찌 (kriii4_V)	C++	6 / 100	1000 ms	94652 KB

V

#include <iostream>
#include <vector>
using namespace std;

typedef long long int ll;

const ll mod = 1000000007LL;

// computes a * b mod n
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;
vector<int> divisors[1048576];
bool is_prime[1048576] = {false};
int euler_phi[1048576];
int pow_k[1048576];
int ans[1048576];

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

	// compute divisors
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j += i)
			divisors[j].push_back(i);

	// 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);

	for (int x = 1; x <= n; x++) {
		int tot = 0;

		// rotation
		for (int i = 0; i < int(divisors[x].size()); i++) {
			int d = divisors[x][i];
			tot = (tot + times_mod(euler_phi[x / d], pow_k[d], mod)) % mod;
		}
		
		// flip
		if (x % 2 == 0) {
			tot = (tot + times_mod(x / 2, pow_k[x / 2 + 1], mod)) % mod;
			tot = (tot + times_mod(x / 2, pow_k[x / 2], mod)) % mod;
		}
		else {
			tot = (tot + times_mod(x, pow_k[(x + 1) / 2], mod)) % mod;
		}
		// cout << tot << endl;

		ans[x] = times_mod(tot, inv_mod(2 * x, mod), mod);
	}

	/*
	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

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

Subtask #2

0.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	39608 KB	Output is correct
2	Correct	6 ms	39608 KB	Output is correct
3	Correct	6 ms	39608 KB	Output is correct
4	Correct	60 ms	43832 KB	Output is correct
5	Execution timed out	1000 ms	94652 KB	Program timed out
6	Halted	0 ms	0 KB	-