整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

繁凡出品的全新系列：解题报告系列 —— 超高质量算法题单，配套我写的超高质量的题解和代码，题目难度不一定按照题号排序，我会在每道题后面加上题目难度指数（ 1 ∼ 5 1 \sim 5 1∼5），以模板题难度 1 1 1 为基准。

---

这样大家在学习算法的时候就可以执行这样的流程：

%
阅读【学习笔记】 / 【算法全家桶】学习算法 ⇒ \Rightarrow ⇒ 阅读相应算法的【解题报告】获得高质量题单 ⇒ \Rightarrow ⇒ 根据一句话题解的提示尝试自己解决问题 ⇒ \Rightarrow ⇒ 点开详细题解链接学习巩固（好耶）
%
要是26个英文字母用完了我就接上24个希腊字母，我就不信50道题不够我刷的hhh

%
解题报告系列合集：【解题报告系列】超高质量题单 + 题解（ICPC / CCPC / NOIP / NOI / CF / AT / NC / P / BZOJ）

本题单前置知识：《算法竞赛中的初等数论》（ACM / OI / MO）前言、后记、目录索引（十五万字符的数论书）

Codeforces - 数学题目泛做（难度：2000 ~ 2800 + ）

题单链接：https://codeforces.com/problemset/page/6?tags=math&order=BY_RATING_DESC

%为了节省篇幅代码我全都放到链接里了（ [https://paste.ubuntu.com/](https://paste.ubuntu.com/)）

专门挑了一些最简单的题写hhh，好像绝大多数都是数论题hhh，后面会慢慢加一些其他的数学题目进来

目录

• 难度：2000 分
• • A. CF803F Coprime Subsequences（容斥原理，莫比乌斯函数）
  • B. CF1033D Divisors（Pollard_rho算法）
  • C. CF1244C The Football Season（拓展欧几里德）
• 难度：2100 分
• • A. CF484B Maximum Value（模运算，优化剪枝枚举）
  • B. CF474F Ant colony（gcd，线段树）
  • C. CF1499D The Number of Pairs（数论，组合数学）
• 难度：2200 分
• • A. CF1327D Infinite Path（置换循环节）
  • B. CF1474D Cleaning（思维套路题）
  • C. CF1485D Multiples and Power Differences （构造）
  • D. CF448E Divisors（爆搜剪枝）
  • E. CF1477C Nezzar and Nice Beatmap（几何，思维）
• 难度：2300 分
• • A. CF1139D Steps to One（期望，杜教筛）
  • B. CF300E Empire Strikes Back（线性筛， 二分）
• 难度：2400 分
• 难度：2500 分
• • A. CF1017F The Neutral Zone（数论 埃氏筛）
• 难度：2600 分
• • A. CF662C Binary Table（矩阵，FWT）
  • B. CF622F The Sum of the k-th Powers（自然数k次幂和，拉格朗日插值）
  • C. CF360D Levko and Sets（容斥）
• 难度：2700 分
• • A. CF906D Power Tower（拓展欧拉定理）
• 难度：2800 分
• • A. CF1208G Polygons（抽象思维，欧拉函数）
• 难度：2900 分
• 难度：3000 分
• • A. CF453D Little Pony and Elements of Harmony（FWT）（3000 分）
• 难度：3100 分
• • A. CF438E The Child and Binary Tree（生成函数，FFT）（3100 分）
• 难度：2000 - 分
• • A. CF1444A Division（唯一分解定理）（1500 分）
  • B. CF1423K Lonely Numbers（思维，分类讨论）（1600 分）
  • C. CF1349A Orac and LCM（gcd）（1600 分）

难度：2000 分

A. CF803F Coprime Subsequences（容斥原理，莫比乌斯函数）

Problem

给定一个 n n n 个数的序列，问你有多少个子序列的 gcd ⁡ = 1 \gcd=1 gcd=1 。

Solution

序列一共有 n n n 个数，显然一共有 2 n − 1 2^n-1 2n−1 个子序列（每个数选或不选减去空集）

考虑容斥。显然答案就是 2 n − 1 2^n-1 2n−1 减去 gcd ⁡ > 1 \gcd>1 gcd>1 的子序列个数，设所有含有大于 1 1 1 的因子的序列中的个数为 x x x ，显然 gcd ⁡ > 1 \gcd>1 gcd>1 的子序列的个数为 2 x − 1 2^x-1 2x−1。显然只与点的权值有关，而 a [ i ] ≤ 1 0 5 a[i]\le 10^5 a[i]≤105，考虑维护权值。设序列中的数的最大值为 m m m。

• 设 c n t i cnt_i cnti​ 表示权值为 i i i 的序列中的数的个数，可以在输入的时候处理一下。

• 设 s u m i sum_i sumi​ 表示含有因子 i i i 的数的个数，显然 s u m i = ∑ i ∣ j c n t j \displaystyle sum_i=\sum\limits_{i|j}{cnt_j} sumi​=i∣j∑​cntj​，即序列中 i i i 的倍数的个数。我们可以通过枚举倍数在 O ( m l o g m ) O(mlogm) O(mlogm) 的复杂度下计算。

• 设 f i f_i fi​ 表示含有因子 i i i 的子序列的个数，显然 f i = 2 s u m i − 1 = 2 ∑ i ∣ j c n t j − 1 \displaystyle f_i=2^{sum_i}-1=2^{\sum\limits_{i|j}{cnt_j}}-1 fi​=2sumi​−1=2i∣j∑​cntj​−1，显然 s u m < m ≤ 1 0 5 sum<m\le10^5 sum<m≤105，我们可以 O ( m ) O(m) O(m) 预处理一下 2 2 2 的次幂。

对于 gcd ⁡ > 1 \gcd>1 gcd>1 的子序列个数，根据奇加偶减的容斥原理，显然为：含有因子 2 2 2 的子序列的个数（ f 2 f_2 f2​） + + + 含有因子 3 3 3 的子序列的个数（ f 3 f_3 f3​） + + + 含有因子 5 5 5 的子序列的个数（ f 5 f_5 f5​） + + + ⋯ \cdots ⋯ − - − 含有因子 2 , 3 2,3 2,3 的子序列的个数（ f 6 f_6 f6​） − - − 含有因子 2 , 5 2,5 2,5 的子序列的个数（ f 10 f_{10} f10​） − ⋯ -\cdots −⋯ + 含有因子 2 , 3 , 5 2,3,5 2,3,5（ f 30 f_{30} f30​） 的子序列的个数 + ⋯ +\cdots +⋯

最终的答案为 2 n − 1 2^n-1 2n−1 减去 gcd ⁡ > 1 \gcd>1 gcd>1 的子序列个数，即变为奇减偶加的形式，然后我们可以发现前面 f x f_x fx​ 的系数实际上就是 μ ( x ) \mu(x) μ(x)（莫比乌斯函数本身就是一个容斥的映射）。

即答案为
2 n − 1 + ∑ i = 2 m μ ( i ) × f i 2^n-1+\sum_{i=2}^{m}\mu(i)\times f_i 2n−1+i=2∑m​μ(i)×fi​

Time

O ( m l o g m ) , m = max ⁡ { a [ i ] } O(mlogm),m=\max\{a[i]\} O(mlogm),m=max{a[i]}

Code

// Problem: CF803F Coprime Subsequences
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF803F
// Memory Limit: 250 MB
// Time Limit: 2000 ms 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int N = 500007, mod = 1e9 + 7;

typedef long long ll;
int n, m, t;
int a[N], mu[N], cnt[N];
bool vis[N];
int primes[N], tot;
int pow2[N];
ll ans;

int add(int a, int b)
{
	return 1ll * a + b >= mod ? 1ll * a + b - mod : 1ll * a + b;
}

int sub(int a, int b)
{
	return a - b < 0 ? a - b + mod : a - b;
}

void init(int n)
{
	pow2[0] = 1, pow2[1] = 2, mu[1] = 1;
	for(int i = 2; i <= n; ++ i) {
		pow2[i] = add(pow2[i - 1], pow2[i - 1]);
		if(vis[i] == 0) {
			primes[ ++ tot] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= tot && i * primes[j] <= n; ++ j) {
			vis[i * primes[j]] = true;
			if(i % primes[j] == 0) {
				mu[i * primes[j]] = 0;
				break;
			}
			mu[i * primes[j]] -= mu[i];
		}
	}
}

int main()
{ 
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		m = max(m, a[i]);
		cnt[a[i]] ++ ;
	}  

	init(N - 7); 
	ans = pow2[n] - 1;
	for(int i = 2; i <= m; ++ i) {
		int sum = 0;
		for(int j = i; j <= m; j += i)  
			sum = (1ll * sum + cnt[j]) % mod; 
		ans = (ans + 1ll * mu[i] * (pow2[sum] - 1) % mod + mod) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}

B. CF1033D Divisors（Pollard_rho算法）

Problem

Solution

我原来珍藏的板子T了可还行

直接Pollard_rho算法进行大数质因子分解，因为要求计算的是 A = ∏ a i A=\prod a_i A=∏ai​ 的因子个数，所以我们计算一下所有质因子的个数 c n t [ i ] cnt[i] cnt[i]，答案显然就是 ∏ ( c n t [ i ] + 1 ) \prod (cnt[i]+1) ∏(cnt[i]+1)（就是对于每一个因子，有不选，选一个，选两个 ⋯ \cdots ⋯，选 c n t [ i ] cnt[i] cnt[i] 个）

1000ms 的时限997ms卡过…

Code

// Problem: D. Divisors
// Contest: Codeforces - Lyft Level 5 Challenge 2018 - Elimination Round
// URL: https://codeforces.com/problemset/problem/1033/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 998244353;

unordered_map <ll, ll> mp;
  
namespace rho{
    const int MAXP = 1000010;
    const int BASE[] = {2, 450775, 1795265022, 9780504, 28178, 9375, 325};

    long long seq[MAXP];
    int primes[MAXP], spf[MAXP];


    long long gcd(long long a, long long b) {
        int ret = 0;
        while(a) {
            for( ; !(a & 1) && !(b & 1); ++ret, a >>= 1, b >>= 1);
            for( ; !(a & 1); a >>= 1);
            for( ; !(b & 1); b >>= 1);
            if(a < b) swap(a, b);
            a -= b;
        }
        return b << ret;
    }

    inline long long mod_add(long long x, long long y, long long m){
        return (x += y) < m ? x : x - m;
    }

    inline long long mod_mul(long long x, long long y, long long m){
        long long res = x * y - (long long)((long double)x * y / m + 0.5) * m;
        return res < 0 ? res + m : res;
    }

    inline long long mod_pow(long long x, long long n, long long m){
        long long res = 1 % m;
        for (; n; n >>= 1){
            if (n & 1) res = mod_mul(res, x, m);
            x = mod_mul(x, x, m);
        }

        return res;
    }

    inline bool miller_rabin(long long n){
        if (n <= 2 || (n & 1 ^ 1)) return (n == 2);
        if (n < MAXP) return spf[n] == n;

        long long c, d, s = 0, r = n - 1;
        for (; !(r & 1); r >>= 1, s++) {}

        for (int i = 0; primes[i] < n && primes[i] < 32; i++){
            c = mod_pow(primes[i], r, n);
            for (int j = 0; j < s; j++){
                d = mod_mul(c, c, n);
                if (d == 1 && c != 1 && c != (n - 1)) return false;
                c = d;
            }

            if (c != 1) return false;
        }
        return true;
    }

    inline void init(){
        int i, j, k, cnt = 0;

        for (i = 2; i < MAXP; i++){
            if (!spf[i]) primes[cnt++] = spf[i] = i;
            for (j = 0, k; (k = i * primes[j]) < MAXP; j++){
                spf[k] = primes[j];
                if(spf[i] == spf[k]) break;
            }
        }
    }

    long long pollard_rho(long long n){
        while (1){
            long long x = rand() % n, y = x, c = rand() % n, u = 1, v, t = 0;
            long long *px = seq, *py = seq;

            while (1){
                *py++ = y = mod_add(mod_mul(y, y, n), c, n);
                *py++ = y = mod_add(mod_mul(y, y, n), c, n);
                if((x = *px++) == y) break;

                v = u;
                u = mod_mul(u, abs(y - x), n);

                if (!u) return gcd(v, n);
                if (++t == 32){
                    t = 0;
                    if ((u = gcd(u, n)) > 1 && u < n) return u;
                }
            }

            if (t && (u = gcd(u, n)) > 1 && u < n) return u;
        }
    }

    vector <long long> factorize(long long n){
        if (n == 1) return vector <long long>();
        if (miller_rabin(n)) return vector<long long> {n};

        vector <long long> v, w;
        while (n > 1 && n < MAXP){
            v.push_back(spf[n]);
            n /= spf[n];
        }

        if (n >= MAXP) {
            long long x = pollard_rho(n);
            v = factorize(x);
            w = factorize(n / x);
            v.insert(v.end(), w.begin(), w.end());
        }

        sort(v.begin(), v.end());
        return v;
    }
} 

signed main() {
    // Q.init(N - 1);//如果代码超时且仅需要分解大数的质因数可以用这句话，否则不要用
    ll T, n;
    rho :: init();
    scanf("%lld", &T);
    while (T--) { 
        scanf("%lld", &n);
        vector <ll> res = rho :: factorize(n); 
        for(auto it : res)
        	mp[it] ++ ;
    }
    ll ans = 1;
    for(auto it : mp)
    	ans = (ans * (it.second + 1)) % mod;
    printf("%lld\n", ans);
    return 0;
}

C. CF1244C The Football Season（拓展欧几里德）

Problem

Berland capital team比了 n n n 场比赛，总得分为 p p p 。已知胜一场得 w w w 分，平局 d d d 分，败了 0 0 0分。

答案表示为（ x ， y ， z x，y，z x，y，z）：表示胜了 x x x 场，平局 y y y 场，败了 z z z 场。使得：

x ∗ w + y ∗ d = p x * w + y * d=p x∗w+y∗d=p
x + y + z = n x+y+z=n x+y+z=n
若无方案则输出 -1。若有多重方案，输出任意一个即可。

1 ≤ n ≤ 1 0 12 , 0 ≤ p ≤ 1 0 17 , 1 ≤ d < w ≤ 1 0 5 1≤n≤10 ^{12} ,0≤p≤10^{ 17} ,1≤d<w≤10^{ 5} 1≤n≤1012,0≤p≤1017,1≤d<w≤105

Solution

这就是 2000 的题嘛，爱了爱了

直接拓展欧几里得算一下最小的这个整数解即可。

数据较大，中间乘的时候肯定会爆 long long 直接开 __int128 就行了。

Code

// Problem: CF1244C The Football Season
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1244C
// Memory Limit: 250 MB
// Time Limit: 1000 ms  
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
typedef __int128 ll;
const int N = 5e5 + 7;

long long n, m, p, w, d;

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if(b == 0) {
		x = 1, y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, x, y);
	ll z = x;
	x = y, y = z - a / b * y;
	return d;
}

int main()
{
	scanf("%lld%lld%lld%lld", &n, &p, &w, &d);
	
	ll x, y, gcd;
	gcd = exgcd((ll)d, (ll)w, x, y); 
	if(p % gcd != 0) {
		puts("-1");
		return 0;
	}  
	ll x0 = w / gcd, y0 = d / gcd; 
	 
	y = ((p / gcd % x0) * (x % x0) % x0 + x0) % x0;
	x = (p - y * d) / w;

 	if(x < 0 || x + y > n) {
		puts("-1");
	}
	else {
		cout << (long long)x << " " << (long long)y << " " << n - (long long)y - (long long)x << endl;
	}
	return 0;
}

难度：2100 分

A. CF484B Maximum Value（模运算，优化剪枝枚举）

Problem

给定一个序列 a i a_i ai​ ，请找出两个数 i , j i,j i,j，使得 a i ≥ a j a_i \ge a_j ai​≥aj​ ，并且使得 a i   m o d   a j a_i \bmod a_j ai​modaj​ 的值最大，求这个 a i   m o d   a j a_i\bmod a_j ai​modaj​ 的最大值。

1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ a i ≤ 1 0 6 1 \le n \le 2\times 10^5,1 \le a_i \le 10^6 1≤n≤2×105,1≤ai​≤106

Solution

我们要找的是最大的 a i   m o d   a j a_i\bmod a_j ai​modaj​。

那么显然有：

a m o d    b = a − ⌊ a b ⌋ × b = a − k × b   ( 设  k = ⌊ a b ⌋ ) a\mod b=a-\lfloor\frac{a}{b}\rfloor\times b=a-k\times b\ (\text{设}\ k=\lfloor\cfrac{a}{b}\rfloor) amodb=a−⌊ba​⌋×b=a−k×b (设 k=⌊ba​⌋)

显然 a m o d    b a\mod b amodb 得到的是余数，值一定 b b b 的简化剩余系内，即 0 ≤ a m o d    b = a − k × b < b 0\le a\mod b=a-k\times b<b 0≤amodb=a−k×b<b，所以一定有

a > k b a < ( k + 1 ) b \begin{aligned}&a>kb&\\ &a<(k+1)b\end{aligned} ​a>kba<(k+1)b​

我们可以枚举 a [ i ] = b a[i]=b a[i]=b，然后枚举倍数 k k k，使得 k b < a , a = max ⁡ { a [ i ] } kb<a,a=\max\{a[i]\} kb<a,a=max{a[i]}，对于枚举到的 b b b 和 k k k ，我们可以直接二分找到最大的小于 ( k + 1 ) b (k+1)b (k+1)b 的数作为 a a a。

复杂度有点问题，考虑优化。首先这里两个相同权值的点的作用显然是完全一样的，所以我们可以先排序去重，这样我们会遇到的最坏的情况的数据就是 1 , 2 , ⋯ n − 1 1,2,\cdots n-1 1,2,⋯n−1，这样枚举 k k k 的均摊复杂度为 n ( n + 1 ) 2 = 1 e 6 , n = 1 e 6 2 = 707 \cfrac{n(n+1)}{2}=1e6,n=\sqrt {\cfrac{1e6}{2}}=707 2n(n+1)​=1e6,n=21e6​ ​=707。

总复杂度为 O ( n l o g n m ) ≈ 2 e 9 O(nlogn\sqrt m)≈2e9 O(nlognm ​)≈2e9 hhh

考虑继续优化：我们可以加上最优化剪枝，当枚举到的 b < a n s b<ans b<ans 的时候，显然求出来的 a m o d    b < b a\mod b<b amodb<b ，所以直接跳过就行了，这样的话我们就可以倒序枚举 b b b，这样我们在遇到的极端数据 1 , 2 , ⋯ n − 1 1,2,\cdots n-1 1,2,⋯n−1 的时候，从大到小枚举，前面被更新了之后，基本上后半段遇到的所有的数都可以直接跳过，亲测效率极高。

优化之后跑的贼快，没有一个点超过150ms，在洛谷的提交记录里能排第二 hhh。

Time

O ( n l o g n m ) , m = max ⁡ { a [ i ] } O(nlogn\sqrt m),m=\max\{a[i]\} O(nlognm ​),m=max{a[i]}

Code

// Problem: CF484B Maximum Value
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF484B
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 7, M = 2e6 + 7, INF = 1e7;

int n, m;
int ans;
int a[N];
int maxx;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		maxx = max(maxx, a[i]);
	}
	sort(a + 1, a + n + 1);
	int num = unique(a + 1, a + n + 1) - a - 1;
	a[num + 1] = maxx;
	
	for(int i = num; i >= 1; -- i) {
		if(a[i] <= ans) continue;

		for(int k = 2; (k - 1) * a[i] <= a[num + 1]; ++ k) {//a > kb
			int val = k * a[i];//k -> k + 1 
			int aa = lower_bound(a + 1, a + num + 2, val) - a - 1;//a < (k + 1)b
			ans = max(ans, a[aa] % a[i]);
		}
	}
	printf("%d\n", ans);
	return 0;
}

B. CF474F Ant colony（gcd，线段树）

Problem

给出一个长度为 n n n 的序列 s s s， q q q 组询问。

每次给定区间 [ l , r ] [l,r] [l,r]。

如果 i , j ∈ [ l , r ] i,j \in [l,r] i,j∈[l,r]， s i ∣ s j s_i|s_j si​∣sj​ 则 i i i 得一分。

问有多少个没有得到满分，即 r − l r-l r−l。

1   ≤   n , t   ≤   1 0 5 , s i ≤ 1 0 9 1 ≤ n,t ≤ 10 ^5,s_i\le 10^9 1 ≤ n,t ≤ 105,si​≤109

Solution

题目中每次询问可以抽象成这样的一个问题：一个序列，问序列中有多少个数可以整除整个序列中所有的数。显然若 x x x 能整除整个序列，则将 x x x 质因数分解以后， x x x 的所有质因子的次方都是整个序列里最小的才能满足整除整个序列，即： x = ∑ i = 1 i = m p i min ⁡ { a i } x=\sum_{i = 1}^{i = m}p_i^{\min\{a_i\}} x=∑i=1i=m​pimin{ai​}​，欸，这玩意不就是序列里的最大公约数嘛（ g c d ( n , m ) = p 1 m i n { α 1 , β 1 } × ⋯ × p k m i n { α k , β k } gcd(n,m)=p_1^{min\{α_1,β_1\}}\times \cdots\times p_k^{min\{α_k,β_k\}} gcd(n,m)=p1min{α1​,β1​}​×⋯×pkmin{αk​,βk​}​ ）

所以我们直接建一个线段树维护一下区间 gcd ⁡ \gcd gcd 以及有多少个数等于区间 gcd ⁡ \gcd gcd 即可。

具体实现就非常简单了：区间 gcd ⁡ \gcd gcd 等于左右儿子哪边的 gcd ⁡ \gcd gcd 就加上哪边的数的个数。

Time

O ( T l o g n l o g s ) O(Tlognlogs) O(Tlognlogs)

Code

// Problem: CF474F Ant colony
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF474F
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;

int n, m, t;
int a[N];

struct node 
{
	int gcd, num;
	int l, r;
}tr[N];

struct ANS
{
	int gcd, num;
}ans;

void pushup(int p)
{
	tr[p].gcd = __gcd(tr[p << 1].gcd, tr[p << 1 | 1].gcd);
	if(tr[p << 1].gcd == tr[p << 1 | 1].gcd) tr[p].num = tr[p << 1].num + tr[p << 1 | 1 ].num;
	else if(tr[p << 1].gcd == tr[p].gcd) tr[p].num = tr[p << 1].num;
	else if(tr[p << 1 | 1].gcd == tr[p].gcd) tr[p].num = tr[p << 1 | 1].num;
	else tr[p].num = 0;
}

void build(int p, int l, int r)
{
	tr[p].l = l, tr[p].r = r;
	if(l == r) {
		tr[p].gcd = a[l];
		tr[p].num = 1;
		return ;
	}
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	pushup(p);
}

ANS query(int p, int l, int r)
{
	ANS tmp;
	if(tr[p].l >= l && tr[p].r <= r) {
		tmp.gcd = tr[p].gcd; 
		tmp.num = tr[p].num;
		return tmp;
	} 
	if(tr[p << 1].r >= r) return query(p << 1, l, r);
	if(tr[p << 1 | 1].l <= l) return query(p << 1 | 1, l, r);  
	ANS res1 = query(p << 1, l, r), res2 = query(p << 1 | 1, l, r);
	tmp.gcd = __gcd(res1.gcd, res2.gcd);
	if(res1.gcd == res2.gcd) tmp.num = res1.num + res2.num;
	else if(tmp.gcd == res1.gcd) tmp.num = res1.num;
	else if(tmp.gcd == res2.gcd) tmp.num = res2.num;
	else tmp.num = 0;
	return tmp;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
	}	
	build(1, 1, n);
	scanf("%d", &m);
	while(m -- ) {
		int l, r;
		scanf("%d%d", &l, &r);
		ans = query(1, l, r);
		printf("%d\n", r - l + 1 - ans.num);
	}
	return 0;
}

C. CF1499D The Number of Pairs（数论，组合数学）

Problem && Solution

Code

// Problem: D. The Number of Pairs
// Contest: Codeforces - Educational Codeforces Round 106 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1499/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms 
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h> 
using namespace std;
#define int long long
typedef pair<int, int>PII;
const int N = 2e7 + 7;
const double PI = acos(-1.0);

int n, t, c, b, x, d;
int m[N];
int primes[N], cnt;
bool vis[N];

void init(int n)
{
    for(int i = 2; i <= n; ++ i) {
        if(vis[i] == 0) {
            primes[ ++ cnt] = i;
            m[i] = 1;
        }
        for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
            vis[i * primes[j]] = true;
            if(i % primes[j] == 0) {
                m[i * primes[j]] = m[i];
                break;
            }
            m[i * primes[j]] = m[i] + 1;
        }
    }
}

int qpow(int a, int b)
{
    int res = 1;
    while(b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int work(int y)
{
    if((y + d) % c) return 0;
    return qpow(2, m[(y + d) / c]);
}

void solve()
{
    int ans = 0;
    scanf("%lld%lld%lld", &c, &d, &x);
    for(int i = 1; i * i <= x; ++ i) {
        if(x % i == 0) {
            ans += work(i);
            //cout << ans << endl;
            if(i * i != x) {
                ans += work(x / i);
            }
        }
    }
    printf("%lld\n", ans);
}

signed main()
{
    init(N - 7);
    scanf("%lld", &t);
    while(t -- ) {
        solve();
    }
    return 0;
}

难度：2200 分

A. CF1327D Infinite Path（置换循环节）

Problem

T 组数据，每组数据给定一个长度为 n n n 的排列（置换） p p p 和颜色数组 c c c，求最小的 k k k，使 p k p^k pk 中存在一个“同色无限环”。即，存在 i i i，使 p i k ,   p p i k k ,   … p^k_i ,\ p_{p^k_i}^k ,\ \dots pik​, ppik​k​, …，整个循环节全部同色。其中 p k p^k pk 指排列 p p p 进行 k − 1 k-1 k−1 次 p p p 置换。

数据范围： 1 ≤ T ≤ 1 0 4 ， 1 ≤ n , ∑ n ≤ 2 × 1 0 5 1\le T\le 10^4 ，1\le n,\sum n\le 2\times 10^5 1≤T≤104，1≤n,∑n≤2×105 。

Solution

显然一个置换可以拆分为若干个循环置换，即若干个循环节，并且每一个循环置换之间是没有任何关联的，所以我们可以每次单独对每一个循环置换进行分析，并且题目要求出现一个同色无限环即可，所以我们单独分析，然后取最小值即可。

这里给定的序列一定是一个排列，所以直接暴力计算所有的循环节，设该循环节的长度为 l e n len len，我们知道对一个循环节进行 k k k 次置换之后，点 i i i 将会指向原序列中的点 i + k i+k i+k。设我们要找的答案为 k k k， k k k 的含义就是所有经过的点是从某个点 i i i 出发，每次走 k k k 步所能到达的所有点的集合。

显然 k ≤ l e n ≤ n k\le len \le n k≤len≤n，我们如果每次暴力枚举 k k k ，时间复杂度 O ( n 2 ) O(n^2) O(n2) 显然无法接受，我们考虑优化。显然可以想到在学习群论的时候有一个定理，在一个长度为 l e n len len 的环上，从 i i i 出发，每次走 k k k 步，等价于从 i i i 出发，每次走 gcd ⁡ ( l e n , k ) \gcd(len, k) gcd(len,k) 步，所以我们只需要枚举所有的 gcd ⁡ ( l e n , k ) \gcd(len, k) gcd(len,k)，即 l e n len len 的因子即可。这样时间复杂度仅为 O ( n × d ( n ) ) ≈ O ( n l o g n ) O(n\times d(n))≈O(nlogn) O(n×d(n))≈O(nlogn)，对于每一个 k k k ，我们判断一下从 i ∈ [ 0 , k ) i\in[0,k) i∈[0,k) 出发，每次走 k k k 步经过的循环节中的点的颜色是否相同即可。

Code

// Problem: D. Infinite Path
// Contest: Codeforces - Educational Codeforces Round 84 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1327/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h> 
using namespace std;

const int maxn = 2e5 + 7, INF = 0x3f3f3f3f;

template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0; 
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
}

template <typename T> void print(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) print(x / 10);
    putchar(x % 10 + 48);
} 
 
int t, n, m, ans;
int a[maxn], col[maxn], tot;
bool vis[maxn];
vector <int> cir;

inline bool work(const int k, const int len)
{
	for(int i = 0; i < k; ++ i) {
		bool flag = true;
		for(int j = i; j < len; j += k) {
			if(col[cir[i]] != col[cir[j]]) {
				flag = false;
				break;
			}
		}
		if(flag) return true;
	}
	return false;
}
 
inline int cal(int k, int len)
{
	if(work(k, len)) return k;
	return INF;
}

int main()
{
	read(t);
	while(t -- ) {  
		ans = INF;
		read(n);
		for(int i = 1; i <= n; ++ i) 
			read(a[i]), vis[i] = 0;
		for(int i = 1; i <= n; ++ i) 
			read(col[i]);
			
		for(int i = 1; i <= n; ++ i) {
			int now = i;
			if(vis[now] == 0) cir.clear();
			else continue;
			while(vis[now] == 0) {
				vis[now] = 1;
				cir.push_back(now);
				now = a[now];
			}
			int len = cir.size();
			for(int i = 1; i * i <= len; ++ i) 
				if(len % i == 0) 
					ans = min({ans, cal(i, len), cal(len / i, len)});					
		}
		print(ans);
		puts("");
	}
	return 0;
}

B. CF1474D Cleaning（思维套路题）

Problem

你有一个长度为 n n n 的数组 a a a。

现在要进行一些操作将数组的所有元素清除：

选定两个下标连续的数，若两个数均不为 0 0 0，则将两个数均减 1 1 1。
在此之前，你可以使用一次超能力（可以不使用）：任选两个下标连续的数并交换。

编写程序，判断是否可以清空 a a a 数组。

Solution

显然根据套路，我们只需要找到哪些是必须交换的，然后看它能不能交换即可。

因为显然交换的位置是在中间，所以我们可以两头扫一遍，先从左往右模拟一遍，一直修改到不能修改为止，标记不合法需要通过交换救命的位置，然后从右往左模拟一遍，找到不合法的位置，由于交换操作只能用一次，所以假设我们只能交换 i i i ，则我们可以交换 i i i 和 i + 1 i+1 i+1 ，那么就变成了 a [ i + 1 ] a[i+1] a[i+1] 与 p r e [ i − 1 ] pre[i-1] pre[i−1] 一起修改， a [ i ] a[i] a[i] 和 s u f [ i + 2 ] suf[i+2] suf[i+2] 一起修改，如果二者修改后权值相同，则整体可以全部清空，否则就无解。

Code

// Problem: D. Cleaning
// Contest: Codeforces - Codeforces Round #696 (Div. 2)
// URL: https://codeforces.com/contest/1474/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500007;

int n, m, t;
int a[N], pre[N], suf[N];

void solve()
{
	scanf("%lld", &n);
	pre[0] = 0, suf[n + 1] = 0;
	for(int i = 1; i <= n; ++ i) {
		scanf("%lld", &a[i]);
		pre[i] = suf[i] = 0;
	}
	
	for(int i = 1; i <= n; ++ i) {
		if(pre[i - 1] != -1) {
			if(a[i] >= pre[i - 1]) 
				pre[i] = a[i] - pre[i - 1];
			else pre[i] = -1;
		}
		else pre[i] = -1;
	}
	for(int i = n; i >= 1; -- i) {
		if(suf[i + 1] != -1) {
			if(a[i] >= suf[i + 1]) 
				suf[i] = a[i] - suf[i + 1];
			else suf[i] = -1;
		}
		else suf[i] = -1;
	}
	if(pre[n] == 0) {//不需要交换
		puts("YES");
		return ;
	}
	for(int i = 1; i < n; ++ i) {
		if(pre[i - 1] != -1 && suf[i + 2] != -1 && pre[i - 1] <= a[i + 1] && suf[i + 2] <= a[i]) {
			if(a[i + 1] - pre[i - 1] == a[i] - suf[i + 2]) {
				puts("YES");
				return ;
			}
		}
	} 
	puts("NO");
	return ;
}

signed main()
{
	scanf("%lld", &t);
	while(t -- ) {
		solve();
	}
	return 0;
}

C. CF1485D Multiples and Power Differences （构造）

Problem

有一个矩阵 a a a ,请你构造一个矩阵 b b b ，使得：

0 < b i , j ≤ 1 0 6 0<b_{i,j}\le 10^6 0<bi,j​≤106

b i , j b_{i,j} bi,j​ 是 a i , j a_{i,j} ai,j​的倍数

b b b 中相邻的两个数的差的绝对值可以写成 k 4 ( k ∈ N + ) k^4(k\in\mathbb{N}^+) k4(k∈N+)

1 ≤ a i , j ≤ 16 1\le a_{i,j}\le 16 1≤ai,j​≤16

Solution

先玩样例：

1 2 
2 3
···
6 2 
2 6

16 16 16
16 16 16
···
16 32 16 
32 16 32

发现首先要考虑的是位置对应，所以我们按照奇数偶数分开，奇行偶列，奇行奇列，偶行奇列，偶行偶列，使用位运算可以将他们分开：

1 ^ 1 = 0    1 ^ 0 = 1
         ↖ ↗
         ↙ ↘
0 ^ 1 = 1    0 ^ 0 = 0

解决了位置放置的问题，再来思考如何求矩阵 b b b。

首先每一个 b i , j b_{i,j} bi,j​ 必须是 a i , j a_{i,j} ai,j​ 的倍数，并且 b i , j ≤ 1 0 6 b_{i,j}\le 10^6 bi,j​≤106，

首先乱搞肯定不行， b b b 种的每一个数都有要求，必须和相邻的格子差值的绝对值为 k 4 k^4 k4 ，但是 k k k 仅需大于 1 1 1 即可，没有其他的要求，啥都行，而 1 ≤ a i , j ≤ 16 1\le a_{i,j}\le 16 1≤ai,j​≤16 所以这就给我们了一个提示， k k k 的取值根据当前的 a a a 来决定。

所以我们必须要同时满足：

首先必须是 a a a 的倍数，然后差值还必须是 k 4 k^4 k4。

因为要的是差值，我们不好控制这个差值，只有当一个数是固定的，这样我们将另一个数加上 k 4 k^4 k4 ，这样我们就可以控制这个差值了，再结合上面我们分析样例，发现确实有一些数是可以不变的，所以我们考虑有没有一个数一定是 a i , j a_{i,j} ai,j​ 的倍数？而 b b b 还有限制 ， b i , j ≤ 1 0 6 b_{i,j}\le 10^6 bi,j​≤106，需要尽量的小，还要一定是全部的倍数 —— 最小公倍数LCM。其实关键在于 1 ≤ a i , j ≤ 16 1\le a_{i,j}\le 16 1≤ai,j​≤16，给定一个很小的小范围， b b b 也有范围，这些都是提示呀各位。我们计算发现 1 1 1 ~ 16 16 16 的 L C M = 720720 ≤ 1 0 6 LCM=720720\le 10^6 LCM=720720≤106，这样还满足了一定是 a i , j a_{i,j} ai,j​ 的倍数，而且还是一个固定的值，这样我们就可以控制两个数的差值，完美！

最后如何控制差值，我们仅需根据最开始奇偶分类， 1 1 1 为 L C M LCM LCM 。 0 0 0 呢，想要 1 1 1 和 0 0 0 的差值是 k 4 k^4 k4 ，而 k k k 任意，所以我们取 0 0 0 位置上的 a i , j a_{i,j} ai,j​ 即可， 0 0 0 的值就是 L C M + ( a i , j ) 4 LCM+(a_{i,j})^4 LCM+(ai,j​)4。

Code

// Problem: D. Multiples and Power Differences
// Contest: Codeforces - Codeforces Round #701 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1485/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
typedef pair<int, int> PII;
const int N = 3e4 + 7, M = 6e6 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;

int lcm(int a, int b)
{
    return a / __gcd(a, b) * b;
}
int n, m, x;
int main()
{
    scanf("%d%d", &n, &m);
    int LCM = 1;
    for(int i = 1; i <= 16; ++ i) {
        LCM = lcm(LCM, i);
    }
    for(int i = 1; i <= n; ++ i) {
        for(int j = 1; j <= m; ++ j) {
            scanf("%d", &x);
            if(((i ^ j) & 1) == 0)//其实无所谓
                printf("%d ", LCM);
            else printf("%d ", LCM + x * x * x * x);
        }
        puts("");
    }
    return 0;
}

D. CF448E Divisors（爆搜剪枝）

Problem

Solution

显然我们应该先预处理出 n n n 的因数，显然 n n n 的因数的因数的因数…一定都是 n n n 的因数，这样我们就可以直接查表了，因为因子数很少，这样我们可以直接从根号优化到log左右，然后直接爆搜，发现爆内存MLE了…

考虑剪枝，发现有问题，若 n = = 1 n==1 n==1 时，显然我们没有继续搜 1 0 5 10^5 105 次方的必要了，因为集合 1 1 1 最后一定输出 1 1 1，我们直接输出 1 1 1 然后 return 即可。否则每一个集合都有因子 1 1 1 ，这样的时间复杂度大概是 O ( n 2 ) O(n^2) O(n2) 的，导致爆搜的时候直接爆掉栈内存。

剪完之后时间复杂度就只有 O ( n l o g n ) O(nlogn) O(nlogn) 的级别了（ 1 ∼ 1 0 10 1\sim 10^{10} 1∼1010 内最多因子数也只有 1 0 4 10^{4} 104 个因子）

Code

// Problem: E. Divisors
// Contest: Codeforces - Codeforces Round #256 (Div. 2)
// URL: https://codeforces.com/problemset/problem/448/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e6 + 7;

int n, m, k, t;
int a[N];
int cnt;
vector <int> factor, res;

void dfs(int n, int k)
{
	if(cnt == 1e5) return ;
	if(k == 0 || n == 1) {
		printf("%lld ", n);
		cnt ++ ;
		return ;
	}
	for(auto it : factor) {
		if(it > n) break;
		if(n % it == 0)  
			dfs(it, k - 1);  
	}
}
 
signed main()
{
	scanf("%lld%lld", &n, &k);
	for(int i = 1; i * i <= n; ++ i) {
		if(n % i == 0) {
			factor.push_back(i);
			if(i * i != n) factor.push_back(n / i);
		}
	}
	sort(factor.begin(), factor.end());
	dfs(n, k);
	return 0;
}

E. CF1477C Nezzar and Nice Beatmap（几何，思维）

Problem F Nezzar and Nice Beatmap

平面上有 n n n 个点（ 3 ≤ n ≤ 5000 3 ≤ n ≤ 5000 3≤n≤5000），请你找到一个点的排列，如 a 1 , a 2 , a 3 , a 4 , ⋯   , a n a_1,a_2,a_3,a_4,\cdots,a_n a1​,a2​,a3​,a4​,⋯,an​，使得这个排列中的任意相邻的三个点 ABC 组成的角 ∠ A B C ∠ABC ∠ABC 是锐角（指 ∠ a 1 a 2 a 3 ， ∠ a 2 a 3 a 4 ， ∠ a 3 a 4 a 5 , ⋯   , ∠ a n − 2 a n − 1 a n ∠a_1a_2a_3，∠a_2a_3a_4，∠a_3a_4a_5,\cdots, ∠a_{n-2}a_{n-1}a_n ∠a1​a2​a3​，∠a2​a3​a4​，∠a3​a4​a5​,⋯,∠an−2​an−1​an​均为锐角）

Solution

题目要求的是输出一个排列，这个排列所有连续的三个点组成的角都是锐角。

我们首先考虑任意三个点

画一个草图：

我们发现一个钝角三角形，除了有钝角以外，还有两个锐角！

也就是说根据我们选择的顺序不同，是一定能找到一个锐角的排列的，也就是说一定是有解的。

我们发现钝角的对边是最长的那一条，如果我们不想要那个钝角，我们把这个最长的对边，变成我们的角边，不就不是钝角了嘛

思路来了，我们从任意一个点出发，在所有没有被选择过的点之中，找到一个跟它距离最远的点，连上，这样把所有最长的对边都变成角边，不就没有钝角了嘛

然后我们扩充到四个点

由于一定存在解，我们每次选择最远的点，这样就不会有钝角啦

考虑证明一下这个解法。

如果对于任意三个点，ABC ，我们已经确定选择了离 A 最远的 B ，离 B 最远的 C，那么 AC 一定小于 AB，那么 B 的对边一定不是最长的边，也就意味着 ∠ABC 一定是锐角（

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef int itn;
const int N = 5e4 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;

struct Point
{
    ll x, y;
    Point(ll x = 0, ll y = 0) : x(x), y(y) { }
}p[N];

typedef Point Vector;
typedef Point POint;
int n, m;
ll ans[N], vis[N];

itn main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
        scanf("%lld%lld", &p[i].x, &p[i].y);
    ans[1] = vis[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        ll maxx = -1;
        ll id = -1;
        for(int j = 1; j <= n; ++ j) {
            if(vis[j] == 0) {
                if(id == -1 || maxx < (p[j].x - p[ans[i - 1]].x) * (p[j].x - p[ans[i - 1]].x) + (p[j].y - p[ans[i - 1]].y) * (p[j].y - p[ans[i - 1]].y)) {
                    maxx = (p[j].x - p[ans[i - 1]].x) * (p[j].x - p[ans[i - 1]].x) + (p[j].y - p[ans[i - 1]].y) * (p[j].y - p[ans[i - 1]].y);
                    id = j;
                }
            }
        }
        ans[i] = id, vis[id] = 1;
    }
    for(int i = 1; i <= n; ++ i) {
        printf("%lld ", ans[i]);
    }
    puts("");
    return 0;
} 

难度：2300 分

A. CF1139D Steps to One（期望，杜教筛）

Weblink

2021年天梯赛 L3-3 可怜的简单题

CF1139D

Problem

Solution

数据较大，要用快速乘不然会爆 long long

Code

#include <bits/stdc++.h>
using namespace std; 
#define ll long long
const int N = 21544400 + 7;

#define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
#define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y) 

ll mod;
int mu[N];
ll smu[N];
bool vis[N];
unordered_map <ll, ll> sum_mu;
int primes[N], cnt;
ll n, m; 

ll mul(ll a, ll b) {
    if (mod <= 1000000000) return a * b % mod;
    else if (mod <= 1000000000000ll) return (((a * (b >> 20) % mod) << 20) + (a * (b & ((1 << 20) - 1)))) % mod;
    else {
        ll d = (ll)floor(a * (long double)b / mod + 0.5);
        ll res = (a * b - d * mod) % mod;
        if (res < 0) res += mod;
        return res;
    }
}

ll qpow(ll a, ll b)
{
	if(mod == 1) return 0;
	ll res = 1;
	a = a % mod;
	while(b) {
		if(b & 1) res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

ll inv(ll x)
{
	return qpow(x, mod - 2);
}

void init(int n)
{
	mu[1] = 1, vis[1] = 1;
	for(int i = 2; i <= n; ++ i) {
		if(vis[i] == 0) {
			primes[ ++ cnt] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
			vis[i * primes[j]] = 1;
			if(i % primes[j] == 0) {
				mu[i * primes[j]] = 0;
				break;
			}	
			mu[i * primes[j]] -= mu[i];
		}
	}	
	for(int i = 1; i <= n; ++ i) 
		smu[i] = plus(smu[i - 1], mu[i]);
	return ;
}

inline ll g_sum(ll x)
{
	return x;
}

inline ll get_sum_mu(ll x)
{
	if(x <= N - 7) return smu[x];
	if(sum_mu.find(x) != sum_mu.end()) return sum_mu[x]; 

	ll ans = 1;
	for(ll l = 2, r; l <= x; l = r + 1) {
		r = x / (x / l); 
		ll tmp = mul((r - l + 1), get_sum_mu(x / l));
		ans = minus(ans, tmp);
	}
	ans = (ans % mod + mod) % mod;
	sum_mu[x] = ans / g_sum(1ll);
	return ans / g_sum(1ll); 
}

void solve(ll m)
{
	ll ans = 1;
	for(ll l = 1, r; l <= m; l = r + 1) {
		r = m / (m / l); 
		ll tmp = mul((get_sum_mu(r) - get_sum_mu(l - 1)), mul(m / l, inv(m - m / l)));
		ans = minus(ans, tmp);
	}  
	ans = (ans + mod) % mod;
	printf("%lld\n", ans);
	return ;
}

signed main()
{ 
	scanf("%lld%lld", &m, &mod);
	if(m == 1) return printf("1\n"), 0;
	init(N - 7);
	solve(m);
	return 0;
}

B. CF300E Empire Strikes Back（线性筛， 二分）

%https://blog.csdn.net/weixin_39453270/article/details/87992647

难度：2400 分

难度：2500 分

A. CF1017F The Neutral Zone（数论 埃氏筛）

%https://blog.csdn.net/CSDNjiangshan/article/details/81536536

难度：2600 分

A. CF662C Binary Table（矩阵，FWT）

Link

https://codeforces.com/contest/662/problem/C

Problem

给你一个 n × m n\times m n×m 的 01 01 01 矩阵，每次操作：你可以挑选任意的某一行或者某一列翻转（ 0 0 0 变 1 1 1， 1 1 1 变 0 0 0 ），然后你需要使得整个矩阵的 1 1 1 的数量尽可能少，问你最少数量是多少。

n ≤ 20 , m ≤ 1 0 5 n≤20,m≤10^5 n≤20,m≤105

Hint

一句话题解： 遇事不决先暴力，因为我们只有每一行或者每一列翻转或者不翻转，所以我们只需要考虑这个矩阵的初始状态以及每一行和每一列的翻转状态就行了。对于状态而言很容易想到状态压缩。我们可以很轻松地得到一个 O ( 2 n × m ) O(2^n\times m) O(2n×m) 的暴力算法，我们只需要状态压缩行翻转状态就行了。但是很明显过不去。那么我们能压缩行，为什么不能压缩列呢？对于行来说，行翻转状态只有 n n n 行 2 n 2^n 2n 种情况，那么对于每一列来说，同样只有 n n n 行 2 n 2^n 2n 种情况，所以我们就可以继续状压，然后发现从原状态到翻转后的状态不就是原状态与翻转状态的异或和吗？我们利用一些贪心的技巧，化简一下答案的式子，再使用经典FWT转换，就可以将问题转化为标砖的 FWT 的问题在 O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度下解决了 ~

Solution

我们发现序列翻转实际上就是全部的数与1做异或操作。我们将矩阵按列压成二进制。

先看数据： n ≤ 20 , m ≤ 1 0 5 n≤20,m≤10^5 n≤20,m≤105

所以我们肯定先考虑 n n n

我们可以先想暴力的做法，因为最多只有 n ≤ 20 n\le 20 n≤20 行，也就是最多只有 2 20 2^{20} 220 种状态，我们就先可以 2 n 2^n 2n 暴力枚举所有的状态（表示
的实际意义就是当前状态是一个二进制数 x x x 表示 n n n 行里，每一行翻转还是不翻转），这样的话对于每一列当前的状态我们都可以
得到，我们只需要再考虑每一列翻转还是不翻转就行了。所以我们对于当前枚举到的行的状态再枚举每一列， a n s ans ans 加上这一列里当前状态的 m i n { n u m 0 , n u m 1 } min\{num_0,num_1\} min{num0​,num1​}

注意本文一共出现了两种状态：

一个是行翻转状态，代表 n n n 行，每一行翻转为 1 1 1，不翻转为 0 0 0，状压之后是一个 n n n 位二进制数 ，共有 2 n 2^n 2n 种。

一个是列状态，尽管一共有 m ≤ 1 0 5 m\le 10^{5} m≤105 列，但是每列只有 n n n 行，同样最多只有 2 n 2^n 2n 种情况。

我们用 X i X_i Xi​ 表示 2 n 2^n 2n 次枚举，枚举到的行翻转状态，每一列的状态实际上就是这一列的 n n n 行表示的是啥， X i X_i Xi​ 就意味着这一列的这 n n n 行将要进行什么样的翻转。

对于任意一列，第 i i i 列的状态为 S i S_i Si​ 。

则第 i i i 列最后经翻转后实际的状态 Y i = S i ⊕ X i Y_i=S_i\oplus X_i Yi​=Si​⊕Xi​。

由于每一列都可以*翻转，那么它翻转还是不翻转取决于这一列的 m i n { n u m 0 , n u m 1 } min\{num_0,num_1\} min{num0​,num1​}。取 0 0 0 的话实际意义就是把这一行翻转成 1 1 1 嘛，题目想要求的是最少数目的 1 1 1 所以取 m i n min min ，这样就贪心地 O ( 1 ) O(1) O(1) 完成了列的翻转 ！

因此我们设 b [ x ] b[x] b[x] 表示列状态（n行） x x x 的 0 / 1 0/1 0/1 的较小值即 m i n { n u m 0 , n u m 1 } min\{num_0,num_1\} min{num0​,num1​}

设当前枚举到的行翻转状态为 n o w now now，则此时的答案为

a n s = ∑ i = 1 m b [ i ⊕ n o w ] ans=\sum_{i=1}^{m}b[i\oplus now] ans=i=1∑m​b[i⊕now]
我们枚举 2 n 2^n 2n 个 n o w now now 答案取最小值即可。

总时间复杂度为 O ( m × 2 n ) \mathcal O(m\times 2^n) O(m×2n)，而 n ≤ 10 , m ≤ 1 0 5 n\le 10,m\le10^5 n≤10,m≤105，肯定是不可行的。

所以考虑优化：

状压枚举行状态是没什么问题， 2 20 2^{20} 220 的复杂度非常的美丽，所以考虑如何优化枚举每一列的这个操作。

发现尽管一共有 m m m 列，每列是 n n n 行，每列的的列状态是一个 n n n 位二进制数，也就意味着一共就只有 2 n 2^{n} 2n 种列状态，我们设 a [ x ] a[x] a[x] 表示列状态为 x x x 的出现次数， b [ x ] b[x] b[x] 表示列状态 x x x 的 0 / 1 0/1 0/1 的较小值即 m i n { n u m 0 , n u m 1 } min\{num_0,num_1\} min{num0​,num1​} ，也就是一列的状态为 x x x 的时候对答案的贡献。

我们同样 2 n 2^{n} 2n 枚举行的翻转状态。

假设当前的行翻转状态为 n o w now now ，我们枚举所有可能出现的列状态，一共只有 2 n 2^n 2n 种，因为我们统计过了每种状态出现次数，所以如果没有这个状态， a [ i ] = 0 a[i]=0 a[i]=0 ，这种行翻转状态 n o w now now 的答案为：
a n s = ∑ i = 0 2 n a [ i ] × b [ i ⊕ n o w ] ans=\sum_{i=0}^{2^n} a[i]\times b[i ⊕ now] ans=i=0∑2n​a[i]×b[i⊕now]
有点 FWT 那味了hhh，因为 i ⊕ n o w = j , i ⊕ j = n o w i\oplus now=j,i\oplus j=now i⊕now=j,i⊕j=now，所以我们可以转一个形式：

设 f [ n o w ] f[now] f[now] 表示行翻转状态为 n o w now now 时候的答案，所以有：

f [ n o w ] = ∑ i ⊕ j = n o w a [ i ] × b [ j ] f[now]=\sum_{i⊕j=now}a[i]\times b[j] f[now]=i⊕j=now∑​a[i]×b[j]

发现这就是 FWT 的模板，直接卷就完了。

复杂度 O ( 2 n × l o g 2 2 n ) = O ( n × 2 n ) O(2^n\times log_22^n)=O(n\times 2^n) O(2n×log2​2n)=O(n×2n)， n = 20 n=20 n=20。完美 ~

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath> 
using namespace std;
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
const int N = (1 << 20) + 7, M = 1e5+ 7, mod = 1e9 + 7;
const ll INF = 4e18;
itn dcnt;
#define de(x) cout << x << " x" << endl
#define de1() cout << ++ dcnt << "ok" << endl
itn t;
int n, m;
ll a[N], b[N], f[N], S[N], num[N];
char s[N];

void XOR(ll *f, int n, int x = 1)
{
    for(int o = 2; o <= n; o <<= 1) {
        for(int i = 0, k = o >> 1; i < n; i += o) {
            for(int j = 0; j < k; ++ j) {
                ll X = f[i + j];
                ll Y = f[i + j + k];
                f[i + j] = X + Y;
                f[i + j + k] = X - Y;
                if(x == -1) {
                    f[i + j] = (X + Y) / 2;
                    f[i + j + k] = (X - Y) / 2;
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) {
        scanf("%s", s + 1);
        for(int j = 1; j <= m; ++ j) {
            if(s[j] == '1')
                S[j] |= 1 << i - 1;
        }//S 是列状态
    }
    for(int i = 1; i <= m; ++ i)
        a[S[i]] ++ ;
    for(int i = 0; i < (1 << n); ++ i)
        num[i] = num[i >> 1] + (i & 1);
    for(int i = 0; i < (1 << n); ++ i)
        b[i] = min(num[i], n - num[i]);
    XOR(a, 1 << n), XOR(b, 1 << n);
    for(int i = 0; i < (1 << n); ++ i)
        f[i] = a[i] * b[i];
    XOR(f, 1 << n, -1);
    ll ans = INF;
    for(int i = 0; i < (1 << n); ++ i)
        ans = min(ans, f[i]);
    printf("%lld\n", ans);
    return 0;
}

B. CF622F The Sum of the k-th Powers（自然数k次幂和，拉格朗日插值）

Problem

求 ∑ i = 1 n i k \sum_{i=1}^n i^k ∑i=1n​ik ， n ≤ 1 0 9 , k ≤ 1 0 6 n \leq 10^9,k \leq 10^6 n≤109,k≤106

Solution

n = k + 2 n=k+2 n=k+2

我们知道对于一个 n n n 次多项式 f ( x ) f(x) f(x) ，若有一个数列 f ( 1 ) , f ( 2 ) , f ( 3 ) , . . . f ( n ) f(1),f(2),f(3),...f(n) f(1),f(2),f(3),...f(n)，多项式差分为 f ( 2 ) − f ( 1 ) , f ( 3 ) − f ( 2 ) , . . . f(2)-f(1),f(3)-f(2),... f(2)−f(1),f(3)−f(2),...，显然有结论：多项式差分是关于 i i i 的 n − 1 n-1 n−1 次多项式。

题中所给的数列自然数k次幂的和，即 f ( i ) = ∑ j = 1 i j k f(i)=\sum_{j=1}^i j^k f(i)=∑j=1i​jk ，进行多项式差分后得到： Δ f ( i ) = ( i + 1 ) k \Delta f(i)=(i+1)^k Δf(i)=(i+1)k ，是一个关于 i i i 的 k k k 次多项式，可以得出结论：原多项式 f ( n ) f(n) f(n) 是一个关于 n n n 的 k + 1 k+1 k+1 次多项式。

即：自然数k次幂的和是一个 k + 1 k+1 k+1 次多项式。

所以我们只需要预处理出 k + 2 k+2 k+2 个点的值 f ( i ) f(i) f(i) ，就可以使用拉格朗日插值法求出 f ( n ) f(n) f(n)。显然我们可以预处理出 0 ∼ k + 2 0\sim k+2 0∼k+2 的 f ( i ) f(i) f(i) 的值，这样得到的是 x x x 取值连续的序列，我们就可以是哟个拉格朗日插值 O ( n ) O(n) O(n) 计算出 f ( n ) f(n) f(n) 的值，即为答案。

Time

O ( k ) O(k) O(k)

Code

#include <bits/stdc++.h> 
using namespace std;

const int N = 1100007, mod = 1e9 + 7;


int read(){
    int s = 0, ne = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') ne = -1; c = getchar();}
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

int qpow(int a, int b)
{
	int res = 1;
	while(b) {
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod; 
		b >>= 1;
	} 
	return res;
}

int n, k;
int s[N], pre[N], suf[N], infact[N], fact[N], ans;

void init(int k)
{
	infact[0] = fact[0] = 1;
	for(int i = 1; i <= k + 10; ++ i)
		fact[i] = 1ll * fact[i - 1] * i % mod;
	infact[k + 10] = qpow(fact[k + 10], mod - 2);
	for(int i = k + 9; i >= 0; -- i)  
		infact[i] = 1ll * infact[i + 1] * (i + 1) % mod;
	infact[0] = 1;
 	
}
 
// i = 1 to n, ∑ i^k

void lagrange(int n, int k)
{ 
	s[0] = 0;
	for(int i = 1; i <= k + 2; ++ i)
 		s[i] = (s[i - 1] + qpow(i, k)) % mod;
	if(n <= k + 2) {
		printf("%d", s[n]);
		return ;
	}
	pre[0] = 1;
	for(int i = 1; i <= k + 2; ++ i)
		pre[i] = 1ll * pre[i - 1] * ((n - i + mod) % mod) % mod;
	suf[k + 3] = 1;
	for(int i = k + 2; i; -- i)
		suf[i] = 1ll * suf[i + 1] * ((n - i + mod) % mod) % mod;
		
	for(int i = 1; i <= k + 2; ++ i) {
		s[i] = 1ll * s[i] * pre[i - 1] % mod * suf[i + 1] % mod * infact[i - 1] % mod * infact[k + 2 - i] % mod;
		if((k + 2 - i) & 1) 
			ans = (1ll * ans - s[i] + mod) % mod;
		else ans = (1ll * ans + s[i]) % mod;
	}
	printf("%d\n", ans);
}
 
int main()
{
	scanf("%d%d", &n, &k);
	init(k);
	lagrange(n, k);
	return 0;
}

C. CF360D Levko and Sets（容斥）

%https://www.icode9.com/content-4-299931.html

难度：2700 分

A. CF906D Power Tower（拓展欧拉定理）

Problem

Solution

板子题？！

Code

难度：2800 分

A. CF1208G Polygons（抽象思维，欧拉函数）

Problem

在圆周上画出 k k k 个内接正多边形，要求 k k k 个正多边形边数不同，且最大的边数不超过 n n n ，使得总顶点数最小。

Solution

题解来源

其中最简真分数指分子小于分母且分子与分母互质的分数。

Code

// Problem: G. Polygons
// Contest: Codeforces - Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)
// URL: https://codeforces.com/problemset/problem/1208/G
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: 繁凡さん https://fanfansann.blog.csdn.net/
// Powered by CP Editor (https://cpeditor.org)


#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1e6 + 7, INF = 0x3f3f3f3f;

int n, m, k;
int a[N];
int primes[N], cnt, phi[N];
bool vis[N];
vector <int> res;

void init(int n)
{
	vis[1] = phi[1] = 1;
	for(int i = 2; i <= n; ++ i) {
		if(vis[i] == 0) {
			primes[ ++ cnt] = i;
			phi[i] = i - 1;
		}
		for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
			vis[i * primes[j]] = 1;
			if(i % primes[j] == 0) {
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
			phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}
	}
} 

int main()
{
	init(N - 7);
	scanf("%d%d", &n, &k);
	ll ans = 0; 
	if(k == 1) return puts("3"), 0;
	for(int i = 3; i <= n; ++ i) 
		res.push_back(phi[i]);
	sort(res.begin(), res.end());
	for(int i = 0; i < k; ++ i) 
		ans += res[i];
	cout << ans + 2 << endl;
	return 0;
}

难度：2900 分

难度：3000 分

A. CF453D Little Pony and Elements of Harmony（FWT）（3000 分）

Problem

Solution

我以前写的题解

难度：3100 分

A. CF438E The Child and Binary Tree（生成函数，FFT）（3100 分）

Problem

Solution

首先我们发现模数为 998244353 998244353 998244353，很自然的想到NTT！！！想到用多项式来求解本题。

具有同样效果的数字还有： 1004535809 、 469762049 … 1004535809、469762049 \dots 1004535809、469762049…

显然： 998244353 → N T T 998244353\to NTT 998244353→NTT（bushi）题目中要求的是权值和为 s s s 方案数，即点集中选取若干个点组成一颗权值和为 s s s 的树的方案数，经典生成函数。我们设序列 f i f_i fi​ 表示权值和为 i i i 的符合条件的二叉树的个数， g i g_i gi​​ 表示权值 i i i 是否包含在 c c c 中，显然有 f 0 = 1 f_0=1 f0​=1，根据题意可得：
f n = ∑ i = 1 n g i ∑ j = 1 n − i f j f n − i − j [ n > 0 ] f_n=\sum_{i=1}^ng_i\sum_{j=1}^{n-i}f_jf_{n-i-j}[n>0] fn​=i=1∑n​gi​j=1∑n−i​fj​fn−i−j​[n>0]

经典操作，输入的时候处理一下 g i g_i gi​ ，经典动规及乘法原理：权值和为 n n n 的方案数 = = = 权值和为 j j j 的方案数 × \times × 权值和为 n − i − j n-i-j n−i−j 的方案数 ×   g i   ( i是否存在 ) \times\ g_i\ (\text{i是否存在}) × gi​ (i是否存在) 我们只需要令 F F F 表示序列 f f f 的生成函数， G G G 表示序列 g g g 的生成函数。 则： F = G × F 2 + 1 F=G\times F^2+1 F=G×F2+1。生成函数 G G G 已经预处理了，求出 F F F 即可。问题变成了一个一元二次方程，显然可以直接使用求根公式： F = 1 ± 1 − 4 G 2 G F=\cfrac{1± \sqrt{1-4G}}{2G} F=2G1±1−4G ​​。 因为 2 G 2G 2G 可能为 0 0 0 不可求逆，所以需要化简移项： F = 2 1 ± 1 − 4 G F=\cfrac{2}{1±\sqrt{1-4G}} F=1±1−4G ​2​。因为 F 0 = 1 , G 0 = 0 F_0=1,G_0=0 F0​=1,G0​=0，代入发现当且仅当符号取 + + + 时初始值成立， 故取 + + + ，即： F = 2 1 + 1 − 4 G F=\cfrac{2}{1+\sqrt{1-4G}} F=1+1−4G ​2​

我们直接多项式开根 + 多项式求逆即可。

Code

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1000007;
const int p = 998244353, gg = 3, ig = 332738118, img = 86583718;
const int mod = 998244353;

template <typename T>void read(T &x)
{
    x = 0;
    register int f = 1;
    register char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    x *= f;
}

int qpow(int a, int b)
{
    int res = 1;
    while(b) {
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

namespace Poly
{
    #define mul(x, y) (1ll * x * y >= mod ? 1ll * x * y % mod : 1ll * x * y)
    #define minus(x, y) (1ll * x - y < 0 ? 1ll * x - y + mod : 1ll * x - y)
    #define plus(x, y) (1ll * x + y >= mod ? 1ll * x + y - mod : 1ll * x + y)
    #define ck(x) (x >= mod ? x - mod : x)//取模运算太慢了

    typedef vector<int> poly;
    const int G = 5;
    const int inv_G = qpow(G, mod - 2);
    int RR[N], deer[2][19][N], inv[N];

    void init(const int t) {//预处理出来NTT里需要的w和wn，砍掉了一个log的时间
        for(int p = 1; p <= t; ++ p) {
            int buf1 = qpow(G, (mod - 1) / (1 << p));
            int buf0 = qpow(inv_G, (mod - 1) / (1 << p));
            deer[0][p][0] = deer[1][p][0] = 1;
            for(int i = 1; i < (1 << p); ++ i) {
                deer[0][p][i] = 1ll * deer[0][p][i - 1] * buf0 % mod;//逆
                deer[1][p][i] = 1ll * deer[1][p][i - 1] * buf1 % mod;
            }
        }
        inv[1] = 1;
        for(int i = 2; i <= (1 << t); ++ i)
            inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
    }

    int NTT_init(int n) {//快速数论变换预处理
        int limit = 1, L = 0;
        while(limit < n) limit <<= 1, L ++ ;
        for(int i = 0; i < limit; ++ i)
            RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1));
        return limit;
    }

    void NTT(poly &A, int type, int limit) {//快速数论变换
        A.resize(limit);
        for(int i = 0; i < limit; ++ i)
            if(i < RR[i])
                swap(A[i], A[RR[i]]);
        for(int mid = 2, j = 1; mid <= limit; mid <<= 1, ++ j) {
            int len = mid >> 1;
            for(int pos = 0; pos < limit; pos += mid) {
                int *wn = deer[type][j];
                for(int i = pos; i < pos + len; ++ i, ++ wn) {
                    int tmp = 1ll * (*wn) * A[i + len] % mod;
                    A[i + len] = ck(A[i] - tmp + mod);
                    A[i] = ck(A[i] + tmp);
                }
            }
        }
        if(type == 0) {
            for(int i = 0; i < limit; ++ i)
                A[i] = 1ll * A[i] * inv[limit] % mod;
        }
    }

    poly poly_mul(poly A, poly B) {//多项式乘法
        int deg = A.size() + B.size() - 1;
        int limit = NTT_init(deg);
        poly C(limit);
        NTT(A, 1, limit);
        NTT(B, 1, limit);
        for(int i = 0; i < limit; ++ i)
            C[i] = 1ll * A[i] * B[i] % mod;
        NTT(C, 0, limit);
        C.resize(deg);
        return C;
    }

    poly poly_inv(poly &f, int deg) {//多项式求逆
        if(deg == 1)
            return poly(1, qpow(f[0], mod - 2));

        poly A(f.begin(), f.begin() + deg);
        poly B = poly_inv(f, (deg + 1) >> 1);
        int limit = NTT_init(deg << 1);
        NTT(A, 1, limit), NTT(B, 1, limit);
        for(int i = 0; i < limit; ++ i)
            A[i] = B[i] * (2 - 1ll * A[i] * B[i] % mod + mod) % mod;
        NTT(A, 0, limit);
        A.resize(deg);
        return A;
    }
    poly poly_sqrt(poly &f, int deg) {//多项式开方
        if(deg == 1) return poly(1, 1);
        poly A(f.begin(), f.begin() + deg);
        poly B = poly_sqrt(f, (deg + 1) >> 1);
        poly IB = poly_inv(B, deg);
        int limit = NTT_init(deg << 1);
        NTT(A, 1, limit), NTT(IB, 1, limit);
        for(int i = 0; i < limit; ++ i)
            A[i] = 1ll * A[i] * IB[i] % mod;
        NTT(A, 0, limit);
        for(int i =0; i < deg; ++ i)
            A[i] = 1ll * (A[i] + B[i]) * inv[2] % mod;
        A.resize(deg);
        return A;
    }
}

using Poly::poly;
using Poly::poly_sqrt;
using Poly::poly_inv;

int n, m, x, k, type;

char s[N];
int cnt;

int main()
{
    Poly::init(18);//2^21 = 2,097,152,根据题目数据多项式项数的大小*调整，注意大小需要跟deer数组同步(21+1=22)

    read(n), read(m);
    poly f(N), g(N), tmp(N);
    for(int i = 0; i < n; ++ i)
        read(x), g[x] = 1;
    tmp[0] = 1;
    for(int i = 1; i <= m; ++ i) tmp[i] = mod - 4 * g[i] % mod;
    g = poly_sqrt(tmp, m + 1);
     ++ g[0];
    f = poly_inv(g, m + 1);
    for(int i = 1; i <= m; ++ i) f[i] = f[i] * 2 % mod;
    for(int i = 1; i <= m; ++ i) printf("%d\n", f[i]);
    return 0;
}

难度：2000 - 分

这里是一些随便找的小于2000分的简单数论

A. CF1444A Division（唯一分解定理）（1500 分）

Problem

给定两个数 p , q p,q p,q，求最大的数 x x x，满足：p % x == 0, x % q != 0

Solution

求出 ≤ p \le p ≤p 的满足条件的最大的数，显然 p p p 是最大的可能答案，所以先来考虑 p p p 能否作为答案。

首先 p % p 一定等于 0 0 0 ，所以当 p % q != 0 时，答案显然为 p p p。

然后我们只需要再考虑 q ∣ p q\mid p q∣p 的情况即可。

显然此时的 p p p 所含有的质因子一定包含了所有 q q q 的质因子， p p p 的质因子的种树一定多于或等于 q q q，且次幂一定都大于等于 q q q。即： p = P 1 α 1 P 2 α 2 ⋯ p=P_1^{\alpha_1}P_2^{\alpha_2}\cdots p=P1α1​​P2α2​​⋯ ， q = P 1 β 1 P 2 β 2 ⋯ q=P_1^{\beta_1}P_2^{\beta_2}\cdots q=P1β1​​P2β2​​⋯， ∀ i , α i ≥ β i \forall i, \alpha_i\ge \beta_i ∀i,αi​≥βi​。为了使得 q ∤ p q\nmid p q∤p，我们只需要让任意一个 p p p 的一个质因子 P P P 的次幂 α i \alpha_i αi​ 小于 q q q 中的该质因子的次幂 β i \beta_i βi​，即可使得 q ∤ p q\nmid p q∤p，去掉后剩余的数取最大值即为答案。

我们只需要将 q q q 质因数分解，用 q q q 的所有质因数将 p p p 一一除去，取最大值即可。

Code

// Problem: A. Division
// Contest: Codeforces - Codeforces Round #680 (Div. 1, based on Moscow Team Olympiad)
// URL: https://codeforces.com/problemset/problem/1444/A
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
using ll = long long;
typedef pair<int, int> PII;
const int maxn = 1e5 + 7;

int n, m, t, ans; 
vector <PII> deer;
 
void solve()
{
	ll p, q; 
	ans = 1;
	deer.clear(); 
	scanf("%lld%lld", &p, &q);
	if(p % q != 0) {
		cout << p << endl;
		return ;
	} 
	for(int i = 2; i * i <= q; ++ i) { 
		int cnt1 = 0;
		if(q % i == 0) {
			while(q % i == 0) {
				cnt1 ++ , q /= i;
			}
			deer.push_back({i, cnt1}); 
		}
	}
	if(q > 1) deer.push_back({q, 1}); 

	int tmpp = p, tmp;
	for(int i = 0; i < (int) deer.size(); ++ i) {
		ll P = deer[i].first; 
		int cnt2 = deer[i].second;
		int cnt1 = 0;
		tmp = tmpp;
		if(p % P == 0) {
			while(p % P == 0) {
				cnt1 ++ , p /= P;
			} 
		}
		int more = cnt1 - cnt2 + 1; 
		while(more -- ) 
			tmp /= P; 
		 ans = max(ans, tmp);
	}    
	cout << ans << endl;
}


signed main()
{ 
	scanf("%lld", &t);
	while(t -- ) {
		solve();
	}
	return 0;
}

B. CF1423K Lonely Numbers（思维，分类讨论）（1600 分）

Problem

我们规定对于两个不同的数字 a , b a,b a,b ，如果 gcd ⁡ ( a , b ) , a gcd ⁡ ( a , b ) , b gcd ⁡ ( a , b ) \gcd(a,b),\dfrac{a}{\gcd(a,b)},\dfrac{b}{\gcd(a,b)} gcd(a,b),gcd(a,b)a​,gcd(a,b)b​ 可以构成一个三角形,那么 a , b a,b a,b 便是一组好朋友。

我们进一步规定，如果在一个集合中，有一数字 k k k 和这个集合中任意一个数字都不是朋友，那么数字 k k k 就是一个孤独数字。

给定一个 包含所有 1 1 1 到 n n n 整数的集合 ，求在该集合中有多少数字是孤独数字。

Solution

能组成三角形，显然有任意两边之和大于第三边，即：

a + gcd ⁡ ( a , b ) 2 > b   a + b > gcd ⁡ ( a , b ) 2   b + gcd ⁡ ( a , b ) 2 > a a + \gcd(a, b)^2 > b\\ \ \\ a + b > \gcd(a, b)^2\\ \ \\ b + \gcd(a, b)^2 > a a+gcd(a,b)2>b a+b>gcd(a,b)2 b+gcd(a,b)2>a

得：
a − b < gcd ⁡ ( a , b ) 2 < a + b a - b < \gcd(a, b)^2 < a + b a−b<gcd(a,b)2<a+b
gcd ⁡ \gcd gcd 相关的问题显然考虑按照 ： { 偶合数，偶质数(2)，奇质数，奇合数 ， 1 } \{\text{偶合数，偶质数(2)，奇质数，奇合数}，1\} {偶合数，偶质数(2)，奇质数，奇合数，1} 进行分类讨论。

• 偶合数
  若 a a a 是偶数，显然任意两个相邻的偶数的 gcd ⁡ \gcd gcd 都是 2 2 2，所以我们可以找到与 a a a 相邻的偶数，即 a + 2 a+2 a+2 或 a − 2 a-2 a−2，（ 若 a = a + 2 则 b = a 若a=a+2则b=a 若a=a+2则b=a） a − b < gcd ⁡ ( a , b ) 2 < a + b ⇒ 2 < 4 < ( 2 a ± 2 ≥ 6 ) a - b < \gcd(a, b)^2 < a + b\Rightarrow2<4<(2a±2\ge6) a−b<gcd(a,b)2<a+b⇒2<4<(2a±2≥6)，即所有的偶数一定能找到另一个数与之形成三角形。

• 偶质数（ 2 2 2）
  显然这里 2 2 2 也一定成立 。

• 奇质数
  a a a 为质数，与除自己倍数以外的所有的数的 gcd ⁡ \gcd gcd 均为 1 1 1 ，显然不能构成三角形，除此之外，自己的倍数，需要满足的条件为 gcd ⁡ ( x , a ) 2 = a 2 < ( x + 1 ) a \gcd(x,a)^2=a^2<(x+1)a gcd(x,a)2=a2<(x+1)a，显然 x > a − 1 x>a-1 x>a−1，即 x x x 最小取 a a a，所以为了满足条件： a 2 − a < a 2 < a 2 + a a^2 - a < a^2 < a^2 + a a2−a<a2<a2+a， { a , a 2 } \{a,a^2\} {a,a2} 是一组能组成三角形的解，除此之外的奇质数一定是孤独数。

• 奇合数
  若 a a a 为合数，显然 a = p 1 α 1 p 2 α 2 ⋯ a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots a=p1α1​​p2α2​​⋯，我们只需要选择唯一分解式中的最小的 p p p，令 a = p × x a=p\times x a=p×x，显然 { a ± p , a } \{a±p,a\} {a±p,a} 能组成三角形，即： a + p − a < ( gcd ⁡ ( a + p , a ) = p ) 2 = p 2 < 2 a + p a + p - a < (\gcd(a+p,a)=p)^2=p^2 < 2a+p a+p−a<(gcd(a+p,a)=p)2=p2<2a+p，故奇合数一定不是孤独数。

• 1
  显然 1 1 1 与任意数的 gcd ⁡ \gcd gcd 均为 1 1 1，所以一定是孤独数。

综上所诉：我们只需要计算 1 ∼ n 1\sim n 1∼n 中有多少个质数，以及满足在 1 ∼ n 1\sim n 1∼n 中有 p 2 p^2 p2 的质数的个数，即 1 ∼ n 1\sim \sqrt n 1∼n ​ 中有多少个质数，我们显然可以直接预处理出所有的质数个数数组 n u m num num，最终的答案为： a n s = n u m [ n ] − n u m [ n ) ] + 1 ans=num[n] - num[\sqrt n)]+1 ans=num[n]−num[n ​)]+1。（加 1 1 1 是因为 1 1 1 也是答案）

Code

// Problem: K. Lonely Numbers
// Contest: Codeforces - Bubble Cup 13 - Finals [Online Mirror, unrated, Div. 1]
// URL: https://codeforces.com/problemset/problem/1423/K
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 7;

int n, m, t;
int primes[maxn], cnt, num[maxn];
bool vis[maxn];

void init(int n)
{
	vis[1] = 1;
	for(int i = 2; i <= n; ++ i) {
		if(vis[i] == 0) {
			primes[ ++ cnt] = i;
			num[i] = 1;
		}
		for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
			vis[i * primes[j]] = 1;
			if(i % primes[j] == 0) break;
		}
	}
	for(int i = 1; i <= n; ++ i) {
		num[i] += num[i - 1];
	}
}

int main()
{
	init(maxn - 7);
	scanf("%d", &t);
	while(t -- ) {
		scanf("%d", &n);
		int down = floor(sqrt(n)); 
		printf("%d\n", num[n] - num[down] + 1);
	}
	return 0;
}

C. CF1349A Orac and LCM（gcd）（1600 分）

Code

// Problem: A. Orac and LCM
// Contest: Codeforces - Codeforces Round #641 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1349/A
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 7;

int n, m;
int a[N];
int suf[N];
int GCD, ans;

signed main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) {
		scanf("%lld", &a[i]);
		GCD = __gcd(GCD, a[i]);
	}	
	for(int i = n; i >= 1; -- i) 
		suf[i] = __gcd(suf[i + 1], a[i]);
	for(int i = 1; i <= n; ++ i) 
		ans = __gcd(ans, a[i] * suf[i + 1]);
	printf("%lld\n", ans / GCD);
	return 0;
}