답안 #130530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130530 2019-07-15T13:16:51 Z ffresh 팔찌 (kriii4_V) C++17
6 / 100
1000 ms 71928 KB
#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);
  ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -