CF - D. Counting Arrays（gcd）

题意 给定一个长度为 n 的数组，如果位置 i 上的数 a[i] 满足 g c d ( i , a [ i ] ) = 1 gcd(i, a[i]) = 1 gcd(i,a[i])=1 的话，那么第 i 个位置可以删除，后面的位置往前移动一个位置。

选择 n 次位置编号将整个数列的所有位置删除，选择的 n 个位置编号构成删除序列。

给定 n，m，问如果 a[i] 的范围为 1~m 的话，对于数组长度 1~n，满足至少有两个删除序列的数组一共有多少个？也就是说，能构造出多少至少有两种删除方案的数组？

2 ≤ n ≤ 3 ⋅ 1 0 5 , 1 ≤ m ≤ 1 0 12 2≤n≤3⋅10^5, 1≤m≤10^{12} 2≤n≤3⋅105, 1≤m≤1012

思路 发现任意一个数组都有一个删除方案：每次删除位置1，删除 n 次。那么就需要再找出一种删除方案即可。 不妨反着考虑，用总的数组个数减去只有一种删除方案的数组个数。

什么样的数组只有一种删除方案呢？ 也就是说，每次只有第一个位置是满足 gcd(i, ai) = 1 的，而且每次删掉第一个位置，后面的位置前移之后，仍然满足。 那么，位置 i 上的数 a[i] 和前面所有位置要都不是互质的，那么 a[i] 就应该是 1~i-1 中所有质数的乘积的倍数。假设前面位置编号中所有质数乘积为 x，当前位置能放的数就有 m/x 种。 第 1 个位置能放 m 种，第 2~n 个位置能放 m / x i m/x_i m/xi 种，把所有位置能放的种类乘起来，便是满足只有一种删除方案的数组个数。 用总的数组数减去只有一种删除方案的数组数便是至少有两种删除方案的数组数。

要额外注意爆 ll 的地方要及时取模。

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 998244353;
int T, n, m;
int a[N];

int qmi(int x, int y)
{
          
   
	x %= mod; //x太大，先取模一下
	int ans = 1;
	while(y)
	{
          
   
		if(y & 1) ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}

signed main(){
          
   
	Ios;
	cin >> n >> m;
	int ans = 0;
	for(int i=2;i<=n;i++) ans = (ans + qmi(m, i)) % mod;
	
	int x = 0;
	int cnt = m, flag = 0; //第一个位置m个数都可以放，cnt初始为m。 
	for(int i=2;i<=n;i++)
	{
          
   
		if(!x) x = i;
		else if(__gcd(x, i) == 1){
          
   
			if(x <= m/i) x *= i; //x*i可能会爆ll
			else break; //前面位置编号中质数的乘积如果超过m了，当前位置就没有数能放，后面位置也不用考虑了 
		}
		cnt = cnt % mod * ((m / x) % mod) % mod; // m/x为当前位置能放的种类数，cnt为前i个位置种类数的乘积。 
		ans = (ans - cnt % mod + mod) % mod; //总的方案数减去长度为i的非法数组数 
	}
	cout << ans;
	
	return 0;
}

细节还是挺多的。