Submission #22279

#	Time	Username	Problem	Language	Result	Execution time	Memory
22279		카시코이 (#40)	Fully Generate (KRIII5_FG)	C++14	2 / 7	500 ms	635800 KiB

FG

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;
const int PMAX = 4e7;
const int QMAX = 70000;

int dp[PMAX + 1]; // dp[i]: i�� ������ �� �� �����ϴ°�?
ll psum[PMAX + 1];
vector<int> deg[QMAX + 1];

ll fastpow(ll x, ll y) {
	if (y == 0) return 1;
	if (y % 2) return x*fastpow(x, y - 1) % MOD;
	ll h = fastpow(x, y / 2);
	return h*h%MOD;
}

int main() {
	ll N; scanf("%lld", &N);

	dp[1] = psum[1] = 1;
	dp[2] = 2;
	psum[2] = 3;
	int j = 2;
	for (int i = 3; i <= PMAX; i++) {
		// find min(j) s.t. psum[j] >= i
		while (psum[j] < i) j++;
		// now psum[j] >= i
		dp[i] = j;
		psum[i] = psum[i - 1] + j;
	}

	int maxint = lower_bound(psum + 1, psum + 1 + PMAX, N) - psum;
	int maxdp = -1;
	for (int i = 2; i < maxint; i++) {
		deg[dp[i]].push_back(i);
		maxdp = max(maxdp, dp[i]);
	}

	ll ans = 1;
	for (int i = 2; i <= maxdp; i++) {
		ll cur = 1;
		for (int x : deg[i]) cur = cur*x%MOD;
		ans = ans*fastpow(cur, i) % MOD;
	}

	ll last = N - psum[maxint - 1];
	ans = ans*fastpow(maxint, last) % MOD;

	printf("%lld", ans);
}

Compilation message (stderr)

FG.cpp: In function 'int main()':
FG.cpp:23:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  ll N; scanf("%lld", &N);
                         ^

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5