Submission #130530

#	Time	Username	Problem	Language	Result	Execution time	Memory
130530		ffresh	팔찌 (kriii4_V)	C++17	6 / 100	1085 ms	71928 KiB

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 (stderr)

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 / 6
• Subtask 2: 0 / 94