Product it again

原题：Product it again

原题大意

给出N，M，让你求出GCD(1, 1) GCD(1, 2) … GCD(1, M) GCD(2, 1) GCD(2, 2) … GCD(2, M) … GCD(N, 1) GCD(N, 2) … GCD(N, M) 结果mod10^9+7。

算法分析

考虑某一个质数p对答案的贡献ans。ans = p^((n/p m/p) + ((n/p^2 m/p^2)) + ….)原理类比n!的质因子分解后，对某个质因子p的指数大小的计数。所以我们只需要一个线性筛即可，然后暴力计数。复杂度约为O((n/logn) logn logn)。
这里有关于n！质因子分解和素数快速筛法的相关博客：

http://www.doc88.com/p-9159772516121.html

http://blog.csdn.net/qq_31917799/article/details/51612654

http://blog.csdn.net/dinosoft/article/details/5829550

程序代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 10000050;
int t,cnt;
ll n,m,p[maxn],ans;
bool tag[maxn];
void getprime(){
    cnt = 0;
    for(int i = 2; i < maxn; i++){
        if(!tag[i])
            p[cnt++] = i;
        for(int j = 0; j < cnt && i*p[j] < maxn;j++)
        {
            tag[i*p[j]] = 1;
            if(!(i%p[j])) break;
        }
    }
}
ll pow(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % mod;
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
ll getcnt(ll p, ll limm, ll limn){
    ll cnt1 = 0;
    ll nex = p;
    while(nex <= min(limm,limn)){
        cnt1 += (limm/nex) * (limn/nex);
        nex *= p;
    }
    return cnt1;
}
int main(){
    memset(tag,false,sizeof(tag));
    getprime();
    scanf("%d", &t);
    while(t--){
        scanf("%lld%lld", &n, &m);
        ans = 1;
        for(int i = 0; i < cnt && p[i] <= min(n,m); i++)
            ans = ans * pow(p[i],getcnt(p[i],m,n)) % mod;
    printf("%lld\n", ans);
    }

    return 0;
}