P1072 Hankson 的趣味题

视频讲解

正在上传B站中

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
int a0,a1,b0,b1;
bool vis[maxn];
int P[maxn],tail;
struct node{
    int a,b,c,d;
};
map<int,node> mp;
void initP(int N){
    for(int i = 2;i<=N;i++){
        if(!vis[i]) P[tail++] = i;
        for(int j = 0;P[j]<=N/i;j++){
            vis[P[j]*i] = true;
            if(i%P[j] == 0) break;
        }
    }
}
void divP(){
    int idx = 0;
    for(int t:{a0,a1,b0,b1}){
        ++idx;
        for(int j = 0;j<tail && P[j]*P[j] <=t;j++){
            if(t%P[j] == 0){
                int cnt = 0;
                while(t%P[j] == 0){
                    cnt++;
                    t/=P[j];
                }
                if(idx == 1) mp[P[j]].a = cnt;
                if(idx == 2) mp[P[j]].b = cnt;
                if(idx == 3) mp[P[j]].c = cnt;
                if(idx == 4) mp[P[j]].d = cnt;
            }
        }
        if(t>1){
            if(idx == 1) mp[t].a = 1;
            if(idx == 2) mp[t].b = 1;
            if(idx == 3) mp[t].c = 1;
            if(idx == 4) mp[t].d = 1;
        }
    }
}
ll fun(){
    ll res = 1;
    for(auto p:mp){
        node cur = p.second;
        int a = cur.a,b = cur.b,c = cur.c,d = cur.d;
        int cnt = 0;
        for(int i = 0;i<=31;i++){
            if(min(i,a) == b && max(i,c) == d) cnt++;
        }
        res *= cnt;
    }
    return res;
}
int main(){
    ios;
    initP(1<<16);
    cin>>T;
    while(T--){
        cin>>a0>>a1>>b0>>b1;
        mp.clear();
        divP();
        cout<<fun()<<endl;
    }
    return 0;
}