2018 CCPC Finals

比赛地址 ：Codeforces Gym 102055

A - Mischievous Problem Setter

签到，排序之后扫一扫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr first 
#define sc second 

#define N 100007

int testcase;

pair<int, int> a[N];

inline void work() {
	printf("Case %d: ", ++testcase);
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) a[i].fr = rd();
	for (int i = 1; i <= n; ++i) a[i].sc = rd();
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++i) {
		if (a[i].sc > m) {printf("%d\n", i - 1); return;}
		m -= a[i].sc;
	}
	printf("%d\n", n);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

*B - Balance of the Force

有 \(n\) 位骑士，现在要分裂成两个阵营，第 \(i\) 位骑士加入光明阵营武力值为 \(L_i\) ，加入黑暗阵营武力值为 \(D_i\) 。

此外有 \(m\) 对仇敌关系 \((x_i,y_i)\) ，表示要求第 \(x_i\) 位骑士不能和第 \(y_i\) 位骑士加入同一阵营。

问是否存在合法划分方案。若存在，假设第 \(i\) 位骑士最终的武力值为 \(w_i\) ，最小化 \(\max w_i-\min w_i\) 。

按照冲突关系连边，如果不是二分图就无解。

否则二分图染色，那么对于一个连通块只有两种染色方案，武力值区间对应着两个不同的 \([l,r]\) 。

不妨设两个区间分别是 \([l_1,r_1]\) 和 \([l_2,r_2]\) 且 \(r_1<r_2\) ，我们先让每个区间取 \([l_1,r_1]\) 。

然后从小到大枚举 \(\min w_i\) ，然后将不合法的区间变成另一个即可，维护过程中最小差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr first 
#define sc second 
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

#define N 200007

int testcase, col[N], a[N], b[N];

vector<int> e[N], s[3];

bool dfs(int u) {
	s[col[u]].pb(u);
	for (auto v : e[u])
		if (!col[v]) {
			col[v] = 3 - col[u];
			if (dfs(v)) return true;
		} else if (col[u] == col[v]) return true;
	return false;
}

int l1[N], r1[N], l2[N], r2[N], tot;

priority_queue<pii, vector<pii>, greater<pii>> q;

inline void work() {
	tot = 0;
	while(!q.empty()) q.pop();
	printf("Case %d: ", ++testcase);
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) {e[i].clear(); col[i] = 0;}
	for (int i = 1; i <= m; ++i) {
		int a = rd(), b = rd();
		e[a].pb(b); e[b].pb(a);
	}
	for (int i = 1; i <= n; ++i) {a[i] = rd(); b[i] = rd();}
	int nwr = 0;
	for (int i = 1; i <= n; ++i) 
		if (!col[i]) {
			s[1].clear();
			s[2].clear();
			col[i] = 1;
			if (dfs(i)) {puts("IMPOSSIBLE"); return;}
			++tot; 
			l1[tot] = l2[tot] = 2e9;
			r1[tot] = r2[tot] = 0;
			for (auto u : s[1]) {
				l1[tot] = min(l1[tot], a[u]);
				l2[tot] = min(l2[tot], b[u]);
				r1[tot] = max(r1[tot], a[u]);
				r2[tot] = max(r2[tot], b[u]);
			}
			for (auto u : s[2]) {
				l1[tot] = min(l1[tot], b[u]);
				l2[tot] = min(l2[tot], a[u]);
				r1[tot] = max(r1[tot], b[u]);
				r2[tot] = max(r2[tot], a[u]);
			}
			if (r1[tot] > r2[tot]) {
				swap(r1[tot], r2[tot]);
				swap(l1[tot], l2[tot]);
			}
			nwr = max(nwr, r1[tot]);
			q.push(mp(l1[tot], tot));
		}
	int ans = 2e9;
	while (!q.empty()) {
		auto [nwl, p] = q.top(); q.pop();
		ans = min(ans, nwr - nwl);
		if (l2[p] == nwl) break;
		q.push(mp(l2[p], p)); nwr = max(nwr, r2[p]);
	}
	printf("%d\n", ans);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

**C - GCD Land

对于 \(1\dots n\) ，构造一个不超过 \(10^n\) 的非负整数，使得 \(x+1,x+2,\dots x+n\) 连通。

定义 \(u,v\) 直接连通当且仅当 \(gcd(u,v)>1\) ，定义 \(u,v\) 连通当且仅当 \(u,v\) 直接连通或存在 \(w\) 使得 \(u,w\) 连通、\(w,v\) 连通。

如果令 \(x=\prod_{p\ is\ prime,p\le n} p - 1\) ，那么数列相当于变成了 \(0,1,\dots,n-1\) ，除了 \(1\) 其他人都和 \(0\) 连通。

那么现在就需要找一个合数沟通 \(1\) 和其他，随便构造一下就好了。注意到素数只有 \(\mathcal{O}(\frac{n}{\ln n})\) 个，数位并不会超。

柴老师的构造在 \(n>34\) 的时候都有解，所以 \([1,34]\) 就打下表。求很多个数字的乘积用分治 + FFT即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;typedef vector<int> PN;
const int maxn=100000,maxt=1<<18,MOD=998244353;

int te,n,P[maxn+5];
int p[maxn+5];bool pri[maxn+5];
int wn[maxt+5],temA[maxt+5],temB[maxt+5];
int m;PN f[maxn+5],F,G,H,res;

void Make(int n){
	for (int i=2;i<=n;i++){
		if (!pri[i]) p[++p[0]]=i;
		for (int j=1,t;j<=p[0] && (t=i*p[j])<=n;j++)
			{pri[t]=true;if (!(i%p[j])) break;}
	}
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
inline int MUL(int x,int y,int MOD) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
int Pow(int w,int b,int MOD) {int s;for (s=1;b;b>>=1,w=MUL(w,w,MOD)) if (b&1) s=MUL(s,w,MOD);return s;}
void NTTPre(){
	int x=Pow(3,(MOD-1)/maxt);
	wn[maxt>>1]=1;
	for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
	for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
	if (f>0){
		for (int k=n>>1;k;k>>=1)
			for (int i=0;i<n;i+=k<<1)
				for (int j=0;j<k;j++){
					int x=a[i+j],y=a[i+j+k];
					a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
					a[i+j]=ADD(x,y);
				}
	} else {
		for (int k=1;k<n;k<<=1)
			for (int i=0;i<n;i+=k<<1)
				for (int j=0;j<k;j++){
					int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
					a[i+j+k]=ADD(x,MOD-y);
					a[i+j]=ADD(x,y);
				}
		for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
		reverse(a+1,a+n);
	}
}
void Print(const PN &a){
	int si=a.size();
	for (int i=si-1;i>=0;i--) putchar(a[i]+48);
	puts("");
}
PN operator * (const PN &a,const PN &b){
	static PN c;
	int n=a.size(),m=b.size(),t;
	for (t=1;t<n+m-1;t<<=1);
	for (int i=0;i<n;i++) temA[i]=a[i];for (int i=n;i<=t;i++) temA[i]=0;
	for (int i=0;i<m;i++) temB[i]=b[i];for (int i=m;i<=t;i++) temB[i]=0;
	NTT(temA,t,1);NTT(temB,t,1);
	for (int i=0;i<t;i++) temA[i]=MUL(temA[i],temB[i]);
	NTT(temA,t,-1);
	for (int i=0;i<n+m-1;i++) temA[i+1]+=temA[i]/10,temA[i]%=10;
	int si=n+m-1;
	while (si>1 && !temA[si]) si--;
	c.resize(si+1);
	for (int i=0;i<=si;i++) c[i]=temA[i];
	return c;
}
PN operator * (const PN &a,const int &x){
	static PN c;
	int si=a.size();
	for (int i=0;i<si;i++) temA[i]=a[i]*x;
	for (int i=si;i<=si+10;i++) temA[i]=0;
	for (int i=0;i<si+10;i++) temA[i+1]+=temA[i]/10,temA[i]%=10;
	si+=10;while (si>1 && !temA[si]) si--;
	c.resize(si+1);
	for (int i=0;i<=si;i++) c[i]=temA[i];
	return c;
}
PN operator + (const PN &a,const PN &b){
	static PN c;
	int n=a.size(),m=b.size(),si=max(n,m);
	for (int i=0;i<n;i++) temA[i]=a[i];
	for (int i=0;i<m;i++) temB[i]=b[i];
	for (int i=n;i<=si;i++) temA[i]=0;
	for (int i=m;i<=si;i++) temB[i]=0;
	for (int i=0;i<si;i++) temA[i]+=temB[i];
	for (int i=0;i<si;i++) temA[i+1]+=temA[i]/10,temA[i]%=10;
	while (si>1 && !temA[si]) si--;
	c.resize(si+1);
	for (int i=0;i<=si;i++) c[i]=temA[i];
	return c;
}
void Fix(PN &a,int x){
	a.clear();
	do a.push_back(x%10),x/=10; while (x);
}
PN Solve(int L,int R){
	if (L==R) return f[L];
	int mid=L+(R-L>>1);
	return Solve(L,mid)*Solve(mid+1,R);
}
int main(){
	NTTPre();Make(maxn);
	for (int i=1,j=1,k=1;i<=maxn;i++){
		while (j*j<i) j++;
		while (k<=p[0] && p[k]<j) k++;
		for (int t=k;t<=p[0];t++)
			if (3*p[t]+1<i && !pri[2*p[t]+1]) {P[i]=p[t];break;}
	}
	scanf("%d",&te);
	for (int t=1;t<=te;t++){
		printf("Case %d: ",t);
		scanf("%d",&n);m=0;
		if (n<=34){
			if (n==1) {puts("0");continue;}
			if (n==17) {puts("2183");continue;}
			if (n==18) {puts("27828");continue;}
			if (n==19) {puts("27827");continue;}
			if (n==20) {puts("87889");continue;}
			if (n==21) {puts("87889");continue;}
			if (n==22) {puts("171053");continue;}
			if (n==23) {puts("171053");continue;}
			if (n==24) {puts("325309");continue;}
			if (n==25) {puts("127373");continue;}
			if (n==26) {puts("323509");continue;}
			if (n==27) {puts("151061");continue;}
			if (n==28) {puts("151061");continue;}
			if (n==29) {puts("151061");continue;}
			if (n==30) {puts("151060");continue;}
			if (n==31) {puts("151059");continue;}
			if (n==32) {puts("151058");continue;}
			if (n==33) {puts("151057");continue;}
			if (n==34) {puts("7106717");continue;}
			puts("-1");continue;
		}
		int A=2*P[n]+1,B=P[n];
		for (int i=1;i<=p[0] && p[i]<=n;i++)
			if (p[i]!=P[n] && p[i]!=(2*P[n]+1)){
				A=MUL(A,p[i],P[n]);B=MUL(B,p[i],2*P[n]+1);
				m++;Fix(f[m],p[i]);
			}
		F=Solve(1,m);
		A=Pow(A,P[n]-2,P[n]);
		B=Pow(B,2*P[n]-1,2*P[n]+1);
		G=F*A;G=G*(P[n]-1);G=G*(2*P[n]+1);
		H=F*B;H=H*P[n];H=H*(P[n]+1);
		res=G+H;
		res[0]--;
		for (int i=0;res[i]<0;i++) res[i]+=10,res[i+1]--;
		while (res.size()>1 && !res.back()) res.pop_back();
		Print(res);
	}
	return 0;
}

G - Pastoral Life in Stardew Valley

对于一个 \(n\times m\) 的矩形，求和：对于每一个子矩形，选择其严格包含的（边界不重合）子矩形方案数。

暴力的做法：枚举子矩形宽度 \(w\) 和高度 \(h\) ，然后暴力求和，发现维护一个前缀和就行了。 \[ ans = \bigg(\sum_{h=3}^n(n-h+1)\sum_{l=1}^{h-2}(h-l+1)\bigg)\bigg(\sum_{w=3}^m(m-w+1)\sum_{r=1}^{w-2}(w-r+1)\bigg) \] 理性分析一下，显然这个题目可以变成两个一维问题答案的乘积。

  • 如果子子矩形宽度是 \(1\) ，那么就要从 \(n\) 中选三个数，分别代表左边界，右边界，子子矩形位置，方案数为 \({n\choose 3}\) 。

  • 如果子子矩形宽度是 \(2\) ，那么就要从 \(n\) 中选四个数，方案数为 \({n\choose 4}\) 。

因此最终答案是 \(({n\choose 3} + {n\choose 4})({m\choose 3} + {m\choose 4})\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N   100007
#define mod 1000000007

namespace Comb {
    int fac[N], ifac[N];
 
    inline int fpow(int x, int t) {
        int res = 1;
        for (; t; t >>= 1, x = 1ll * x * x % mod)
            if (t & 1) res = 1ll * res * x % mod;
        return res;
    }
 
    inline void init() {
        fac[0] = ifac[0] = 1;
        for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
        ifac[N - 1] = fpow(fac[N - 1], mod - 2);
        for (int i = N - 2; i; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
    }
 
    inline int C(int n, int m) {
        if (n < m) return 0;
        return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
    }
}

inline int calc(int x) {
    return (Comb::C(x, 3) + Comb::C(x, 4)) % mod;
}

int main() {
    Comb::init();
    for (int t = rd(), i = 1; i <= t; ++i) 
        printf("Case %d: %lld\n", i, 1ll * calc(rd()) * calc(rd()) % mod);
    return 0;
}

I - Cockroaches

二维平面上 \(n\) 个给定点，选一个位置可以把 \(x\) 或 \(y\) 相同的所有点都打上标记。

对于一次操作：（1）求最多标记多少个点。（2）在保证标记点数最多的前提下，有多少个可能的不同的被标记点集。

离散化，记录 \(x\) 相同的最多点数 \(mxx\) ，\(y\) 相同的最多点数 \(mxy\) ， \(cnt[x]+cnt[y]=mxx+mxy\) 的给定点数 \(tot\) ，讨论：

  • 如果 \(tot < mxx\times mxy\) ，那么答案就是 \((mxx+mxy, mxx\times mxy-tot)\) 。
  • 否则（1）答案就要减一，（2）的答案要继续统计 \(cnt[x]+cnt[y]=mxx+mxy-1\) 的个数讨论。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define fr first 
#define sc second 
#define pb push_back
#define all(x) x.begin(), (x).end()

#define N 100007

int testcase, x[N], y[N], cntx[N], cnty[N];

vector<int> X, Y;

inline void work() {
	printf("Case %d: ", ++testcase);
	X.clear(); Y.clear();
	int n = rd();
	for (int i = 1; i <= n; ++i)  {
		cntx[i] = cnty[i] = 0;
		x[i] = rd(); X.pb(x[i]);
		y[i] = rd(); Y.pb(y[i]);
	}
	sort(all(X)); X.erase(unique(all(X)), X.end());
	sort(all(Y)); Y.erase(unique(all(Y)), Y.end());
	auto getx = [&](int w) {return lower_bound(all(X), w) - X.begin() + 1;};
	auto gety = [&](int w) {return lower_bound(all(Y), w) - Y.begin() + 1;};
	int mxx = 0, mxy = 0;
	for (int i = 1; i <= n; ++i) {
		x[i] = getx(x[i]); y[i] = gety(y[i]);
		++cntx[x[i]]; mxx = max(mxx, cntx[x[i]]);
		++cnty[y[i]]; mxy = max(mxy, cnty[y[i]]);
	}
	int cntmxx = 0, cntmxy = 0, cntnxx = 0, cntnxy = 0;
	for (int i = 1; i <= n; ++i) {
		if (cntx[i] == mxx) ++cntmxx;
		else if (cntx[i] == mxx - 1) ++cntnxx;
		if (cnty[i] == mxy) ++cntmxy;
		else if (cnty[i] == mxy - 1) ++cntnxy;
	}
	int tot = 0, ans = mxx + mxy, totnx = 0;
	for (int i = 1; i <= n; ++i) {
		if (cntx[x[i]] + cnty[y[i]] == ans) ++tot;
		else if (cntx[x[i]] + cnty[y[i]] == ans - 1) ++totnx;
	}
	bool fl = true;
	if (tot == 1ll * cntmxx * cntmxy) {--ans; fl = false;}
	if (ans == 1) {puts("1 1"); return;}
	if (ans == 2) {printf("%d %lld\n", 2, 1ll * n * (n - 1) / 2); return;}
	if (fl) printf("%d %lld\n", ans, 1ll * cntmxx * cntmxy - tot);
	else printf("%d %lld\n", ans, tot + 1ll * cntmxx * cntnxy + 1ll * cntmxy * cntnxx - totnx);
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

*K - Mr. Panda and Kakin

现在定义一个加密 FLAG 的算法（RSA）：

  1. 随机从 \([10^5,10^9]\) 中选取整数 \(x\) 。

  2. 令 \(p\) 为小于 \(x\) 的最大质数，\(q\) 为大于 \(x\) 的最小质数，\(n=pq\)

  3. 令 \(c=\text{FLAG}^{(2^{30}+3)}\mod n\)

现在给定 \(c,n\) ，求 FLAG 。

密码学讲过类似的破解思路但是考场上两个小时的时候才想起来。。。

首先 \(n=pq\) ，其中 \(p,q\) 为相邻素数，所以从 \(\sqrt n\) 开始枚举复杂度不会错，根据唯一分解，第一次找到的因数就是对的。

然后就可以分成两个同余方程，最后用 CRT 合并一下。

破解思路：根据费马小定理有 \(\text{FLAG} = \text{FLAG}^{(2^{30}+3)(2^{30}+3)^{-1}\mod (p-1)}\mod p\)

然后暴力检验一下 \(2^{30}+3\) 是素数，所以可以用扩欧求模 \(p-1\) 下的逆元，然后还原回去就好了。

赛时一直 WA ，发现了胖胖的黑科技快速乘有 bug ，乘数不能超过模数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
typedef long double DB;

int te;LL n,C;

inline ULL ADD(ULL x,ULL y,ULL MOD) {return x+y>=MOD?x+y-MOD:x+y;}
inline ULL MUL(ULL x,ULL y,ULL MOD){
    LL s=x*y-(ULL)((DB)1/MOD*x*y)*MOD;
    return s<0?s+=MOD:(s>=MOD?s-=MOD:s);
}
LL Pow(LL w,LL b,LL MOD) {LL s;for (s=1;b;b>>=1,w=MUL(w,w,MOD)) if (b&1) s=MUL(s,w,MOD);return s;}
LL exgcd(LL a,LL b,LL &x,LL &y){
    if (!b) {x=1;y=0;return a;}
    LL r=exgcd(b,a%b,y,x);y-=a/b*x;
    return r;
}
LL Inv(LL A,LL C){
    LL x,y;exgcd(A,C,x,y);
    return (x%C+C)%C;
}
LL Solve(LL A,LL B,LL C){
    LL x,y,r=exgcd(A,C,x,y);
    C/=r;x=(x%C+C)%C;x=MUL(B/r%C,x,C);
    return x;
}
int main(){
    scanf("%d",&te);
    for (int t=1;t<=te;t++){
        printf("Case %d: ",t);
        scanf("%lld%lld",&n,&C);
        LL S=sqrt(n) - 5;
        while ((n%S)) S++;
        LL Q=S,P=n/S;
        LL INV=Inv((1<<30)+3,P-1);
        LL A=Pow(C%P,INV,P);
        INV=Inv((1<<30)+3,Q-1);
        LL B=Pow(C%Q,INV,Q);
        LL now=Solve(Q,((A-B)%P+P)%P,P);
        A=ADD(MUL(now,Q,n),B,n);
        printf("%lld\n",A);
    }
    return 0;
}

L - Ultra Weak Goldbach's Conjecture

给一个数字 \(x\) ，尝试分成六个素数的和。

偶数：\(2,2,2,2,x,y\) ，奇数：\(2,2,2,3,x,y\) ，剩下的事情交给哥德巴赫猜想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
typedef long double DB;
const int maxn=10000,prime[]={2,3,5,7,11,13,17,19,23,29,31,37};

int te;LL n;
int p[maxn+5];bool pri[maxn+5];
bool f[6][maxn+5];pair<int,int> lst[6][maxn+5];

inline ULL ADD(ULL x,ULL y,ULL MOD) {return x+y>=MOD?x+y-MOD:x+y;}
inline ULL MUL(ULL x,ULL y,ULL MOD){
	LL s=x*y-(ULL)((DB)1/MOD*x*y)*MOD;
	return s<0?s+=MOD:(s>=MOD?s-=MOD:s);
}
LL Pow(LL w,LL b,LL MOD) {LL s;for (s=1;b;b>>=1,w=MUL(w,w,MOD)) if (b&1) s=MUL(s,w,MOD);return s;}
bool check(LL p,LL n){
	int k=0;LL d=n-1,x,s;
	while (d&1^1) d>>=1,k++;
	x=Pow(p,d,n);
	for (;k;k--,x=s){
		s=MUL(x,x,n);
		if (s==1) return x==1 || x==n-1;
	}
	return false;
}
bool MR(LL n){
	if (n==1) return false;
	for (int t=0;t<12;t++){
		if (n==prime[t]) return true;
		if (!(n%prime[t])) return false;
		if (!check(prime[t],n)) return false;
	}
	return true;
}
void Make(int n){
	for (int i=2;i<=n;i++){
		if (!pri[i]) p[++p[0]]=i;
		for (int j=1,t;j<=p[0] && (t=i*p[j])<=n;j++)
			{pri[t]=true;if (!(i%p[j])) break;}
	}
}
int main(){
	Make(maxn);
	f[0][0]=true;
	for (int i=1;i<=5;i++)
		for (int k=1;k<=p[0];k++)
			for (int j=p[k];j<=maxn;j++)
				if (f[i-1][j-p[k]]) f[i][j]=true,lst[i][j]=mp(i-1,j-p[k]);
	scanf("%d",&te);
	for (int t=1;t<=te;t++){
		scanf("%lld",&n);
		printf("Case %d:",t);
		if (n<=11) {puts(" IMPOSSIBLE");continue;}
		LL x=n-10;
		for (;!MR(x) || !f[5][n-x];x--);
		int i=5,j=n-x;
		while (i || j){
			int x=lst[i][j].fr,y=lst[i][j].sc;
			printf(" %d",j-y);
			i=x;j=y;
		}
		printf(" %lld\n",x);
	}
	return 0;
}