Submission #22327

#	Time	Username	Problem	Language	Result	Execution time	Memory
22327		카시코이 (#40)	Fully Generate (KRIII5_FG)	C++98	7 / 7	359 ms	470412 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];
ll D[QMAX + 1];

ll fastpow(ll x, ll y) {
	ll ret = 1;
	while (y) {
		if (y & 1) ret = ret*x%MOD;
		x = x*x%MOD;
		y >>= 1;
	}
	return ret;
}

int main() {
	ll N; scanf("%lld", &N);
	for (int i = 1; i <= QMAX; i++) D[i] = 1;

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

	int maxint = lower_bound(psum + 1, psum + 1 + K, N) - psum;
	for (int i = 2; i < maxint; i++) {
		D[dp[i]] = D[dp[i]] * i;
		D[dp[i]] %= MOD;
	}

	ll ans = 1;
	for (int i = 2; i <= dp[maxint - 1]; i++) {
		ll cur = D[i];
		ans = ans*fastpow(cur, i);
		ans %= 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:26: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: 5 / 5