DZY Loves Math 系列题解

EDT back
题目名称题号标签
DZY Loves Math3309莫比乌斯反演
DZY Loves Math II3462组合数学+背包
DZY Loves Math III3481--
DZY Loves Math IV3512--
DZY Loves Math V3560--
DZY Loves Math VI3561--
DZY Loves Math VII3568--

DZY Loves Math

题意 $$\begin{aligned} n &= {p_1}^{q_1}p_2^{q_2}...p_k^{q_k}\\ \text{Let}~~~f(n)&=max_{i=1}^{k}(q_i)\\ \text{ans}&=\sum_{i=1}^{a} \sum_{j=1}^{b}f(gcd(i,j)))\\ \end{aligned}$$ 多组询问$\text{ans}$,询问次数$\leq 1e4, a, b \leq 1e7$

题解

套路题, Mobius反演化一下式子。 $$ \begin{aligned} \text{ans}&=\sum_{i=1}^{a} \sum_{j=1}^{b}f((i,j))\\ &=\sum_{k=1}^{min(a,b)}f(k)\sum_{i=1}^{a} \sum_{j=1}^{b}[(i,j)=k]\\ &=\sum_{k=1}^{min(a,b)}f(k)\sum_{k|t}^{min(a,b)}\lfloor \frac{a}{t} \rfloor \lfloor \frac{b}{t} \rfloor \mu(\frac{t}{k})\\ &=\sum_{t=1}^{min(a,b)}\lfloor \frac{a}{t} \rfloor \lfloor \frac{b}{t} \rfloor\sum_{d|t}f(d)\mu(\frac{t}{d}) \end{aligned} $$ 预处理$pre[t]$表示$\sum_{d|t}f(d)\mu(\frac{t}{d})$
#include<bits/stdc++.h>

using namespace std;

inline int read(){
	char ch = getchar(); int u = 0,  f = 1;
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
	return u * f;
}

const int maxn = 1e7 + 5;
int pri[maxn], fl[maxn], cnt[maxn];
typedef long long ll;
ll g[maxn], val[maxn];

inline void sieve(){
	for (int i = 2; i < maxn; ++i) {
		if (!fl[i]) pri[++pri[0]] = i, cnt[i] = 1, val[i] = i, g[i] = 1;
		for (int j = 1; j <= pri[0] && i * pri[j] < maxn; ++j){
			fl[i * pri[j]] = 1;
			if (i % pri[j] == 0) {
				cnt[i * pri[j]] = cnt[i] + 1;
				val[i * pri[j]] = val[i] * pri[j];
				assert(val[i] != 0);
				int now = i / val[i];
				if (now == 1) g[i * pri[j]] = 1;
				else g[i * pri[j]] = (cnt[now] == cnt[i * pri[j]] ? -g[now] : 0); 
				break;
			}
			cnt[i * pri[j]] = 1;
			val[i * pri[j]] = pri[j];
			g[i * pri[j]] = (cnt[i] == cnt[i * pri[j]] ? -g[i] : 0); 
		}
	}
	for (int i = 1; i < maxn; ++i) g[i] += g[i - 1]; 
}

int main(){
	//freopen("data.txt","r",stdin);
	sieve();
	int T = read();
	while (T--){
		int a = read(), b = read();
		if (a > b) swap(a, b);
		ll ans = 0;		
		int Last;
		for (int i = 1; i <= a; i = Last + 1){
			Last = min(a / (a / i), b / (b / i));
			ans += 1ll * (a / i) * (b / i) * (g[Last] - g[i - 1]);
		}	
		printf("%lld\n", ans);
	}
	return 0;
}

DZY Loves Math II

题意 题解

因为只能出现因数的倍数次,可以把每个质因数的贡献看成$St_i+r_i$的形式。

$$\text{infact}~~~~{p_i}=t_i*S+r_i~~~~(r_i< S)\\n=k\times S + (n-k*S)\\ \begin{cases}\sum t_i=k\\\sum r_i=(n-k*S)\end{cases}$$

由于$k$的合法取值不会大于$m$,可以考虑枚举$k$。

对于前面一部分,相等于把$k$个球放入$|prime|$个盒子可空的方案数,为$\binom{k+|prime|-1}{|prime|-1}$;

对于后面一部分,因为值域较小而每个质数个数取值是有限的,是一个完全背包计数问题,需要利用单调队列优化背包的方式优化复杂度,需要滚动数组和前缀和。

然后把两部分相乘后相加。

#include <bits/stdc++.h>
using namespace std;
#define IL inline
typedef long long ll;
IL ll read() {
	char ch = getchar(); ll u = 0, f = 1;
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
	return u * f;	
}
const int maxn = 2e6 + 10;
const int mod = 1e9 + 7;
int inv[10]; 
IL int pls(int x, int y) { x += y; return x >= mod ? x - mod : x; }
IL int dec(int x, int y) { x -= y; return x <  0   ? x + mod : x; }
IL int mul(int x, int y) { return 1ll * x * y % mod; } 
IL int fpw(int x, int y, int r = 1) { for (; y; y >>= 1, x = mul(x, x)) if (y & 1) r = mul(r, x); return r; }
int S, q; bool GG = false;
IL void getPrime(int S, vector<int>&p) {
	for (int i = 2; i * i <= S; ++i) {
		bool fl = 0;
		if  (S % i == 0) {
			S /= i; p.push_back(i);
			if (S % i == 0) {
				GG = 1; 
				return;	
			}
		}
	}
	if (S != 1) p.push_back(S);
}
int f[maxn << 3], g[maxn << 3];
IL void dp(vector<int>&pr) {
	g[0] = 1;
	for (int i = 0; i < pr.size(); ++i) {
		int Limit = (S / pr[i]) - 1; 
		memcpy(f, g, sizeof f); memset(g, 0, sizeof g);

		for (int st = 0; st < pr[i]; ++st) {
			int cr = 0;
			for (int j = 0; j <= (S * pr.size() - st) / pr[i]; ++j) {
				cr = pls(cr, f[j * pr[i] + st]); 
				if (j > Limit) cr = dec(cr, f[(j - Limit - 1) * pr[i] + st]);
				g[j * pr[i] + st] = cr;
			}
		}	
/*
		for (int j = pr[i]; j <= pr.size() * S; ++j) {
			for (int k = 1; k <= (S / pr[i]) - 1; ++k) {
				if (pr[i] * k > j) continue;
					g[j] = pls(g[j], f[j - k * pr[i]]);
			}
		}
*/
	}
}
IL int C(ll a, int b) {
	int r = 1;
	for (ll s = a - b + 1; s <= a; ++s) r = mul(r, s % mod);
	for (int i = 2; i <= b; ++i) r = mul(r, inv[i]);
	return r; 
}
signed main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	S = read(), q = read();
	GG = 0; vector<int>pr; getPrime(S, pr);
	dp(pr); ll Sum = 0; 
	for (int i = 0; i < pr.size(); ++i) Sum += pr[i];
	int m = pr.size();
	for (int i = 2; i <= m; ++i) inv[i] = fpw(i, mod - 2);
	while (q--) {
		ll n = read(); int ans = 0; 
		if (GG || Sum > n) { puts("0"); continue; }
		n -= Sum;
		ll Div = n / S; ll rem = n % S;
		for (int i = 0; i <= min(Div, (ll)m - 1); ++i) {
			ans = pls(ans, mul(C(Div - i + m - 1, m - 1), g[S * i + rem])); 
		}
		cout << ans << endl;
	}
	return 0;	
}

CC BY-NC 4.0 2018 © EDT