题目大意
给出N,统计满足下面条件的数对(a,b)的个数:
1.1≤a<b≤N
2.a+b整除a*b
解题报告
首先这道题的复杂度是不对的…
反正能过qwq。
我觉得 这位dalao的题解 写得非常妙啊, 当然同时安利一下看我的题解…
首先考虑题目给出的条件, [latex](a+b)|ab[/latex]
设\(d=gcd(a,b)\), 那么有:$$ \frac{a+b}{d} | \frac{ab}{d} $$
接下来证明当\( a \)和\(b\)互质时, \(a+b\)和\(ab\)互质:
设\(a\)和\(b\)互质且\(a+b\)和\(ab\)有公共质因子\(k\), 那么有\(k|a\)或者\(k|b\)。
假设\(k|a\)那么可得$$a=qk \Rightarrow a+b = qk+b \Rightarrow k|(qk+b) \Rightarrow k|b \Rightarrow k|gcd(a,b)$$
假定不成立, \(a+b\)和\(ab\)必须互质。
继续化简条件, 设[latex]a=\frac{a}{d}, b=\frac{b}{d}[/latex]:
$$ (a+b) | abd $$
由(a+b)和ab互质可得:
$$ (a+b) | d $$
由于\(b*d\le N \)并且\((a+b)|d\), 所以\(b\le m, m=\sqrt{N}\), 题目等价于统计:
$$ \sum_{b=1}^{m}\sum_{a=1}^{b-1}[gcd(a, b) == 1]\lfloor \frac{N}{b(a+b)} \rfloor $$
接下来利用
莫比乌斯函数
进行化简关键一步!
根据莫比乌斯函数性质有$$ (\sum_{d|n}\mu(d)) = [n == 1] $$
那么用这个性质代替gcd(a, b)等于1的约束, 化成:
$$ \sum_{b=1}^{m}\sum_{a=1}^{b-1}(\lfloor \frac{N}{b(a+b)} \rfloor \sum_{d|gcd(a, b)}\mu(d)) $$
枚举\(gcd(a, b)\)因子\(d\), 设\(a=d\cdot a, b=b\cdot d\), 将后面一坨提前:
$$ \sum_{d=1}^m \sum_{b=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{a=1}^{b-1} \lfloor \frac{N}{d^2b(a+b)} \rfloor $$
最后一坨[latex]\lfloor \frac{N}{d^2b(a+b)} \rfloor[/latex]只有[latex]\sqrt{N}[/latex]种取值, 分段计算, 暴力搞就可以了。
代码
#include <cstdio> #include <cstring> #include <climits> #include <cstdlib> #include <algorithm> #include <iostream> #include <cmath> using namespace std; typedef long long LL; inline int getInt () { int ret; char ch; bool flg = false; while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-'); ret = ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch-'0'); return flg ? -ret : ret; } const int MAXN = 100010; int mu[MAXN], prec[MAXN/3], ptot; bool isnprime[MAXN]; inline void linerShaker () { mu[1] = 1; for(int i = 2; i<MAXN; i++) { if(!isnprime[i]) { prec[++ptot] = i; mu[i] = -1; } for(int j = 1; j <= ptot && (LL)i*prec[j] < MAXN; j++) { isnprime[i*prec[j]] = true; if(i%prec[j] == 0) break ; mu[i*prec[j]] = -mu[i]; } } } int main () { LL ans = 0; linerShaker(); int N = getInt(), M = floor(sqrt(N)); for(int d = 1; (LL)d<=M; d++) { LL tmp = 0; for(int b = 2; (LL)b*d<=M; b++) { // t = a+b for(int t = b+1; t<(b<<1); t++) { if(N/((LL)d*d*b*t) == 0) break; LL nxt = min((LL)(b<<1)-1, (N/(N/((LL)d*d*b*t)))/(d*d*b)); tmp += (nxt-t+1)*(N/((LL)d*d*b*t)); t = nxt; } } ans += mu[d]*tmp; } cout << ans << endl; }
Join the discussion