Submission #130530

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
130530	2019-07-15T13:16:51 Z	ffresh	팔찌 (kriii4_V)	C++17	6 / 100	1000 ms	71928 KB

V

#include <stdio.h>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>
#include <queue>
#include <string.h>
#include <string>
#include <set>
#include <memory.h>
#include <functional>
#include <bitset>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
const int N = 1e6 + 2;

vector<int> divisor[N];
int pp[N];

int dp[N], v[N], bit[N];
int getSz(int y) {
	int ret = y;
	int vv,d = pp[y];
	for (int i = 0; i<divisor[d].size(); ++i) {
		vv = divisor[d][i];
		if (bit[vv]==0) {
			vv *= -1;
		}
		ret -= y / vv;
	}
	return ret;
}
int add(int x, int y) {
	int ret = (x + y) % mod;
	if (ret<0) {
		ret += mod;
	}
	return ret;
}
int mul(int x, int y) {
	return (ll)x*y%mod;
}

int ret[N];

bool isNotPrime[N];

int inv[N * 2];
void solve() {
	int n, k;
	scanf("%d %d", &n, &k);
	int i, j;

	int maxi = 0;
	for (int i = 1; i <= n; ++i) {
		pp[i] = 1;
	}

	for (i = 2; i <= n; ++i) {
		bool isPrime = !isNotPrime[i];
		for (j = i; j <= n; j += i) {
			if (isPrime) {
				bit[j] ^= 1;
				pp[j] *= i;
			}
			isNotPrime[j] = true;
		}
	}
	for (i = 2; i <= n; ++i) {
		if (pp[i] == i) {
			for (j = i; j <= n; j += i) {
				if (pp[j] == j) {
					divisor[j].push_back(i);
				}
			}
		}
	}

	int y, g, x;
	v[0] = 1;
	inv[0] = inv[1] = 1;
	int lx = n * 2;
	for (i = 2; i <= lx; ++i) {
		inv[i] = mul(inv[mod%i], (mod - mod / i));
	}
	for (i = 1; i <= n; ++i) {
		v[i] = mul(v[i - 1], k);
	}
	for (i = 1; i <= n; ++i) {
		y = 1;
		for (j = i; j <= n; j += i,++y) {
			if (dp[y] == 0) {
				dp[y] = getSz(y);
			}
			ret[j] = add(ret[j], mul(dp[y], v[i]));
		}
	}
	
	int R=1;
	for (x = 1; x <= n; ++x) {
		if (x & 1) {
			ret[x] = add(ret[x], mul(x, v[(x + 1) / 2]));
		}
		else {
			ret[x] = add(ret[x], mul(x / 2, add(v[x / 2], v[x / 2 + 1])));
		}
		ret[x] = mul(ret[x], inv[x*2]);
		R = add(R, ret[x]);
	}
	printf("%d\n", R);
}

int main() {
	solve();
}

Compilation message

V.cpp: In function 'int getSz(int)':
V.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<divisor[d].size(); ++i) {
                  ~^~~~~~~~~~~~~~~~~~
V.cpp: In function 'void solve()':
V.cpp:57:6: warning: unused variable 'maxi' [-Wunused-variable]
  int maxi = 0;
      ^~~~
V.cpp:82:9: warning: unused variable 'g' [-Wunused-variable]
  int y, g, x;
         ^
V.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	24000 KB	Output is correct
2	Correct	23 ms	23800 KB	Output is correct
3	Correct	24 ms	23800 KB	Output is correct
4	Correct	23 ms	23800 KB	Output is correct
5	Correct	25 ms	23928 KB	Output is correct
6	Correct	23 ms	23928 KB	Output is correct
7	Correct	23 ms	23800 KB	Output is correct
8	Correct	24 ms	23800 KB	Output is correct
9	Correct	23 ms	23800 KB	Output is correct
10	Correct	23 ms	23928 KB	Output is correct
11	Correct	23 ms	23928 KB	Output is correct
12	Correct	23 ms	23800 KB	Output is correct
13	Correct	23 ms	23928 KB	Output is correct
14	Correct	23 ms	23928 KB	Output is correct
15	Correct	24 ms	23956 KB	Output is correct
16	Correct	23 ms	23800 KB	Output is correct
17	Correct	25 ms	23928 KB	Output is correct
18	Correct	23 ms	23800 KB	Output is correct
19	Correct	24 ms	23800 KB	Output is correct
20	Correct	24 ms	23800 KB	Output is correct

Subtask #2

0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	24056 KB	Output is correct
2	Correct	24 ms	23848 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	51 ms	26900 KB	Output is correct
5	Correct	708 ms	59896 KB	Output is correct
6	Correct	902 ms	67832 KB	Output is correct
7	Correct	671 ms	57820 KB	Output is correct
8	Correct	867 ms	66204 KB	Output is correct
9	Execution timed out	1085 ms	71928 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-