Submission #22302

#	Time	Username	Problem	Language	Result	Execution time	Memory
22302		팀명을 한번 정하면 못바꿀까? (#40)	Fully Generate (KRIII5_FG)	C++14	7 / 7	253 ms	118304 KiB

FG

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <string.h>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
typedef long long ll;
typedef pair<int, int> pi;

const int MAX_K = 1e7, CAL_K = 31347587, MOD = 1e9 + 7;

int G[MAX_K+1]; ll Sum[MAX_K+1];
int getG(ll v) {
//	if(v <= MAX_K) return G[v];
//	else {
		int ix = lower_bound(Sum+1, Sum+MAX_K+1, v) - (Sum);
		return ix;
//	}
}
int ab(int a, int b) {
	int res = 1, val = a;
	while(b) {
		if(b%2) res = 1ll * res * val % MOD;
		val = 1ll * val * val % MOD;
		b/=2;
	}
	return res;
}
int main() {
	G[1] = 1; G[2] = 2; G[3] = 2;
	for(int ix=4, k=3; ix<=MAX_K;) {
		for(int p=0; p<G[k]; p++) if(ix+p <= MAX_K) G[ix+p] = k;
		ix += G[k]; k++;
	}
	ll sum = 0;
	for(int i=1; i<=MAX_K; i++) {
		sum += G[i];
		Sum[i] = sum;
	}

	ll N; scanf("%lld", &N);
	int ans = 1, ix = 1;
	for(int i=1; ;) {
//		int cnt = getG(i);
		if(Sum[ix] < i) ix++;
		int cnt = ix;
		if(i % 100000 == 0) printf("%d\n", i);

		int jx = ix, last = -1, multi = 1;
		for(int j=i; ; j++) {
			if(Sum[jx] < j) jx++;
			if(jx != ix) break;
			if(N >= cnt) {
				N -= cnt;
				last = j;
				multi = 1ll * multi * j % MOD;
			}
			else break;
		}
//		printf("[%d - %d] last %d [%d]\n", i, last, last, N);
		if(last != -1)
			ans = 1ll * ans * ab(multi, cnt) % MOD;
		else {
			ans = 1ll * ans * ab(i, N) % MOD;
			break;
		}
		i = last + 1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

FG.cpp: In function 'int main()':
FG.cpp:48: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