首页 > 代码库 > counting the numbers
counting the numbers
题意：
给定$a,b,c$ ,求解满足 $1 \leq m \leq b, 1 \leq n \leq c, a | mn$ 的 $(m,n)$ 数对个数。
$a \leq INTMAX$, $b \leq LONGLONGMAX$
解法
原问题相当于求解 $mn \ mod \ a \equiv 0$ 的数对个数。
$(m \ mod \ a) n \ mod \ a \equiv 0$
这样$m$ ,实际有效的是 $m \ mod \ a$。
这样我们可以将原问题中的 $m$ 分为 $[\frac{b}{a}]$ 段 $m \equiv 1\ to \ a (mod \ a)$，
与一段 $m \equiv 1 \ to(b \mod \ a) (mod \ a)$
考虑求解 $m ∈ [1,t]$ 的 $(m,n)$ 数对个数 $F(t)$。
这样有$$ans = [b/a]F(a) + F(b \ mod \ a)$$
$$F(t) = \sum_{m=1}^t { [\frac{c}{ \frac{a}{(a,m)} }] }$$
记 $d = (m,a)$
$$F(t) = \sum_{d|a}{ [\frac{c}{ \frac{a}{d} }] (the\ cnt\ of\ m\ that (m,a) = d) }$$
$$F(t) = \sum_{d|a}{ [\frac{c}{ \frac{a}{d} }] (the\ cnt\ of\ m\ that (\frac{m}{d},\frac{a}{d}) = 1) }$$
$$F(t) = \sum_{d|a}{ [\frac{c}{ \frac{a}{d} }] (the\ cnt\ of\ i\ that (i,\frac{a}{d}) = 1 and i \leq [\frac{t}{d}]) }$$
后者可以通过容斥$O(\sqrt {\frac{a}{d}})$ 求
#include <bits/stdc++.h> #define LL long long #define bit(x) (1<<(x)) #define P 1000000007LL using namespace std; LL b,c; int a,num[11]; LL calc(int n,int m) //1~n中和 m互质的数字个数 { if(n==0) return 0LL; int tmp = m; int tot = 0; for(int i=2;i*(LL)i<=(LL)m;i++) { if(tmp%i==0) { while(tmp%i==0) tmp/=i; num[++tot] = i; } } if(tmp>1) num[++tot] = tmp; LL ans = 0; for(int S=0;S<(1<<tot);S++) { int tmp = 1,k = 1; for(int i=0;i<tot;i++) if(bit(i)&S) tmp *= num[i+1], k = -k; ans += k * (n/tmp); } return ans % P; } LL calc(int t) { if(t == 0) return 0LL; LL ans = 0; for(int d=1;d*(LL)d<=(LL)a;d++) if(a%d==0) { int tmpd = d; ans += (c / (a/tmpd)) % P * calc(t/tmpd,a/tmpd) % P; if(ans >= P) ans -= P; if(d*d != a) { tmpd = a/d; ans += (c / (a/tmpd)) % P * calc(t/tmpd,a/tmpd) % P; if(ans >= P) ans -= P; } } return ans; } int main() { while(cin>>a>>b>>c) { LL ans = (b/a)%P * calc(a)%P + calc(b%(LL)a)%P; cout << ans % P << endl; } return 0; }
counting the numbers