#1163032 (C++17) No.3532 Non-Fourth-Power Sets

• 問題: No.3532 Non-Fourth-Power Sets
• ユーザー: 👑 potato167
• 提出日時: 2026-05-04 23:52:00
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,338 bytes
• コンパイル時間: 2,024 ms
• コンパイル使用メモリ: 221,832 KB
• 実行使用メモリ: 11,988 KB
• 最終ジャッジ日時: 2026-05-04 23:53:08
• 合計ジャッジ時間: 21,498 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	-- * 1
other	TLE * 1 -- * 19

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using pq_ = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}

#include <atcoder/modint>
using mint = atcoder::modint1000000007;

//a以下の素数を列挙、計算量:Nlog(log(N))
vector<int> Eratosthenes(int a){
    if(a<2) return {};
    vector<int> p(a+1,1),ans;
    p[0]=0,p[1]=0;
    int k=2;
    while(k*k<=a){
        if(p[k]){
            ans.push_back(k);
            for(int i=2;i*k<=a;i++){
                p[i*k]=0;
            }
        }
        k++;
    }
    while(k<=a){
        if(p[k]) ans.push_back(k);
        k++;
    }
    return ans;
}

auto E = Eratosthenes(5000);

void solve();
// DEAR MYSTERIES / TOMOO
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
    int A, B;
    cin >> A >> B;
    vector<int> p;
    for (auto x : E) {
        if (A == 1) break;
        if (A % x == 0) {
            p.push_back(0);
            while (A % x == 0) {
                A /= x;
                p.back()++;
            }
        }
    }
    if (A != 1) p.push_back(1);
    mint ans = 1;
    for (auto x : p) {
        x *= B;
        x++;
        // cout << "# " << x << endl;
        vector<mint> dp = {1};
        rep(rp, 0, x) {
            vector<mint> n_dp(rp + 2);
            rep(i, 0, rp + 1) {
                n_dp[i + 1] += dp[i];
                n_dp[i] += dp[i] * (i - rp / 4);
            }
            swap(n_dp, dp);
            // for (auto y : dp) cout << y.val() << " ";
            // cout << endl;
        }
        ans *= vec_sum(dp);
    }
    cout << ans.val() << "\n";
}

/*
 * 一つ目の条件について、
 * z が S に含まれているなら
 * x, y = z とすることで自明に成り立つので、
 * S に含まれていない任意の正整数について、
 * この条件を満たさないようにしないといけない
 *
 * x = gp, y = gq としたとき、
 * z / g, gpq / z が互いに素な整数になる？
 * z / g = a とおくと、
 * g / z = 1 / a より
 * gpq / z = pq / a
 * 結局、pq の約数を入れてあげないといけないことになる
 * いやそうではないのか
 * pq の約数であって、素べきの指数が pq と一致もしくは 0 のものは取れる
 *
 * よって、集合は g, と長さ m の (p, e) の列で表され、
 * 集合の大きさは 2^m になるはず...
 * いや、1, 2, 3, 4, 6, 12 という集合もいけるはず
 * (p, (e1, e2, ... , en)) の列で表せるのか
 *
 *
 * 二つ目の条件について、
 * x = gp, y = gq としたとき、
 * lcm(x, y) / gcd(x, y) = pq であることから、
 * これが 4 乗数なのは、p, q どちらも 4 乗数であるということになる
 * min(p, q) != 1
 *
 * (p, (e1, ... en)) という列で表すとき、
 * (e1, ... , en) の中に mod 4 で等しいものは存在しないということになる
 *
 * w(x, y) って、素因数であって同じ数でないものが何個あるか
 * みたいな話になる
 * それを最小化するためには、
 * Y 側はなるべく、同じものを選ぶべきである
 * つまり、任意の素因数について、
 * e が完全一致か完全不一致ということになる
 *
 * つまり、
 * (0, 1, ... , B) を 適当に分割する方法が何通りかを求めればいい
 * サンプルは合いました
 * つまり、ここの高速化さえできればいい
 * 前計算だろうな
 * second スターリング数の亜種みたいになる
 * まず、スターリング数の総和の egf は exp(exp(x) - 1) らしい
 * それはそうかその中での並び替えとあれだから
 * スターリング数ですらこの大変さなのに、計算できるのだろうか
 *
 * 解けねー
 *
 */