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[];

LL calc(int n,int m)    //1~n中和 m互质的数字个数

{

    if(n==) return 0LL;

    int tmp = m;

    int tot = ;

    for(int i=;i*(LL)i<=(LL)m;i++)

    {

        if(tmp%i==)

        {

            while(tmp%i==) tmp/=i;

            num[++tot] = i;

        }

    }

    if(tmp>) num[++tot] = tmp;

    LL ans = ;

    for(int S=;S<(<<tot);S++)

    {

        int tmp = ,k = ;

        for(int i=;i<tot;i++) if(bit(i)&S) tmp *= num[i+], k = -k;

        ans += k * (n/tmp);

    }

    return ans % P;

}

LL calc(int t)

{

    if(t == ) return 0LL;

    LL ans = ;

    for(int d=;d*(LL)d<=(LL)a;d++)

        if(a%d==)

        {

            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 ;

}

巴特西

counting the numbers

最新文章

热门文章