| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19752 |
2016-02-25T05:16:39 Z |
Qwaz |
팔찌 (kriii4_V) |
C++ |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
