Submission #22896

#	Time	Username	Problem	Language	Result	Execution time	Memory
22896		pichulia	Fully Generate (KRIII5_FG)	C++98	7 / 7	246 ms	3932 KiB

FG

#include<stdio.h>
#define M 1000000007
#define X 60009
int m;
int gl;
long long int n;
long long int a[X+1][2];
long long int g[X+1][2];
long long int gs[X+1];
int get_index(long long int x)
{
	int l, r, mid;
	l = 1; r = m;
	while (l < r) {
		mid = (l + r) / 2;
		if (a[mid][0] <= x) {
			if (a[mid][1] > x)
				return mid;
			l = mid + 1;
		}
		else
		{
			r = mid;
		}
	}
	return l;
}
void inil()
{
	long long int i, j, k, l;
	a[1][0] = 1;
	a[1][1] = 2;
	a[2][0] = 2;
	a[2][1] = 4;
	m = 3;
	j = 4;

	// a[i][0] <= x < a[i][1] --> g[x] = i
	for (i = 3; i < X; i++) {
		k = get_index(i);
		a[i][0] = j;
		a[i][1] = j + k;
		j += k;
		m++;
	}

	// g[i][0] <= x < g[i][1] --> 
	// g[x] == gs[i] + (x - g[i][0]) / i
	g[1][0] = 1;
	g[1][1] = 2;
	g[2][0] = 2;
	g[2][1] = 6;
	g[3][0] = 6;
	g[3][1] = 12;
	g[4][0] = 12;
	g[4][1] = 24;
	gs[1] = 1;
	gs[2] = 2;
	gs[3] = 4;
	gs[4] = 6;
	gs[5] = 9;
	gl = 5;
	j = 24;
	for (i = 5; i < X; i++) {
		k = get_index(i);
		g[i][0] = j;
		g[i][1] = j + k*i;
		j = j + k*i;
		gs[i + 1] = gs[i] + k;
		if (j > 1000000000000LL) {
			gl = i + 1;
			break;
		}
	}
}
long long int d[X];
long long int exp(long long int p, int q) {
	long long int r = 1;
	long long int z = p;
	while (q) {
		if (q & 1) { r = (r*z) % M; }
		z = (z*z) % M;
		q /= 2;
	}
	return r;
}
void precess()
{
	int i, j, k, l;
	d[1] = 1;
	for (i = 2; i < gl; i++) {
		d[i] = 1;
		k = get_index(i);
		for (j = 0; j < k; j++) {
			d[i] = (d[i] * (gs[i] + j)) % M;
		}
		d[i] = exp(d[i], i);
		d[i] = (d[i - 1] * d[i]) % M;
	}
}
int get_gindex(long long int x) {
	int l, r, mid;
	l = 1; r = gl;
	while (l < r) {
		mid = (l + r) / 2;
		if (g[mid][0] <= x) {
			if (g[mid][1] > x) {
				return mid;
			}
			l = mid + 1;
		}
		else
		{
			r = mid;
		}
	}
	return l;
}
int main() {
	inil();
	precess();
	scanf("%lld", &n);
	if (n == 1) {
		printf("1\n");
		return 0;
	}
	int gi = get_gindex(n);
	long long int res = d[gi - 1];
	long long int k = (n - g[gi][0]) / gi;
	for (int i = 0; i < k; i++) {
		res = (res * exp(gs[gi] + i, gi)) % M;
	}
	long long int si;
	si = g[gi][0] + gi*k;
//	printf("%lld %lld %d\n", k, si, gi);
	for (; si <= n; si++) {
		res = (res * (gs[gi] + k)) % M;
	}
	printf("%lld\n", res);
	return 0;
}

Compilation message (stderr)

FG.cpp: In function 'void inil()':
FG.cpp:30:25: warning: unused variable 'l' [-Wunused-variable]
  long long int i, j, k, l;
                         ^
FG.cpp: In function 'void precess()':
FG.cpp:89:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
FG.cpp: In function 'int main()':
FG.cpp:122:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
                   ^

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