Product it again

题意：求解 $$\prod_{1 \leq i \leq n} \prod_{1 \leq j \leq m} {(i,j)}$$

解法：

满脑子的反演

考虑对于第一个质数 $p$ 的贡献为 $p^{[\frac{n}{p}][\frac{m}{p}] + [\frac{n}{p^2}][\frac{m}{p^2}] ... }$

这样1~n的质数大概有$O(\frac{n}{logn})$，对于每一个质数$O(logn)$，总效率大概为 $O(n)$

#include <iostream>

#include <cstdio>

#include <cstring>

#define LL long long

#define N 10000010

#define P 1000000007LL

using namespace std;

int n, m, tot, prime[N];

bool v[N];

LL qpow(LL x, LL n)

{

    LL ans = ;

    for(; n; n >>= , x = x * x % P)

        if(n & )

            ans = ans * x % P;

    return ans;

}

int main()

{

    int T;

    for(int i = ; i < N; i++)

        if(!v[i])

        {

            prime[++tot] = i;

            for(int j = i+i; j < N; j += i)

                v[j] = ;

        }

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d %d", &n, &m);

        if(n > m) swap(n, m);

        LL ans = ;

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

            if(prime[i] <= n)

            {

                LL tmp = prime[i];

                LL cnt = ;

                while(tmp <= n)

                {

                    cnt += (n/tmp) * (m/tmp);

                    tmp *= prime[i];

                }

                ans = ans * qpow(prime[i], cnt) % P;

            }

        printf("%lld\n", ans);

    }

}

巴特西

Product it again

最新文章

热门文章