#if defined(__GNUC__) && !defined(__clang__) #pragma GCC optimize("O3") #if defined(__x86_64__) || defined(__i386__) #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #endif #endif #include #include #include #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() using namespace std; using namespace atcoder; using ll=long long; using ull=unsigned long long; using ld=long double; using vll=vector; using vvll=vector; using vi=vector; using vvi=vector; using pll=pair; using pi=pair; // using mint=modint998244353; using mint=modint1000000007; // using mint2=static_modint<2>; // using mint=LazyMontgomeryModInt<998244353>; using vm=vector; using vvm=vector; using bint=boost::multiprecision::uint512_t; /** * O(M(L)*logL) = O(Llog^2 L) * (ここ L は A,C の合計ビット長、M(L) は乗算の計算量) * * 1. 求める量 * 素数 p に対し、v_p(X) を X に含まれる p の指数とする。 * Y>=2 に対して * * rho(X,Y) = min_{p|Y} v_p(X)/v_p(Y) * * と定義する。素因数の指数を比較すると、 * * Y^k | X^n <=> k <= n*rho(X,Y) * * よって求める値は floor(B*rho(A,C)) であり * 以下、Ratio(X,Y) で rho(X,Y) を求める。 * * 2. 整数部分の除去と gcd の置き換え * theta=rho(X,Y) とし、q=floor(theta) とおく。 * q は Y^q | X となる最大の整数なので、割り切れるだけ Y で割れば * * theta = q+rho(X/Y^q,Y) * * となる。以降、X を X/Y^q に置き換えれば 0<=rho(X,Y)<1 * 実装では Y,Y^2,Y^4,... を用いる strip で q を高速に求める。 * * さらに、0<=rho(X,Y)<1 ゆえ * * rho(gcd(X,Y),Y) = min(rho(X,Y),1) = rho(X,Y) * * なので、X を gcd(X,Y) に置き換えて良い * これで X|Y, X a/(c-k*a) = (a/c)/(1-k*(a/c)) * * と変化する。 * Y \nmid X^k より k*theta<1 なので、最小比 theta を達成する素数は残る。 * また g(t)=t/(1-k*t) は 0<=t<1/k で単調増加するため、 * 最小比を取ってもこの変形が成立する。 * * よって beta=rho(X,Y') を再帰的に求めれば、 * * theta = beta/(1+k*beta) * * と復元できる。 * * 4. k の選択 * k を単に小さく選ぶだけでは、再帰が十分速く進むとは限らない * そこで k=1,2,4,... と倍増させ、次を満たす k を選ぶ。 * * Y \nmid X^k, Y | X^(2k) * * X^k mod Y を繰り返し二乗すれば O(log log Y) 回で探索できる。 * theta>0 なら Y | X^floor(log_2 Y) なので、 * 見つからなければ theta=0 と判定できる。 * * この k の選び方が計算量の鍵になる * X|Y かつ k>=1 より X|h * また Y|X^(2k) より、各素因数の指数を比較すると Y|h^2 * したがって * XY | h^3 * => h >= (XY)^(1/3) * => X*Y' = XY/h <= (XY)^(2/3) * * が成立する * * 合計ビット長の尺度を s = log_2 X + log_2 Y = log_2 XY とすると * * s' = log_2(X*Y') <= (2/3)log_2(XY) = (2/3)s * * 再帰ごとに合計ビット長が定数倍以下に減少する。 */ int strip(bint&X,const bint&P){ if(X%P!=0)return 0; int q=2*strip(X,P*P); if(X%P==0){ X/=P; q++; } return q; } pi Ratio(bint X,const bint&Y){ int q=strip(X,Y); X=boost::multiprecision::gcd(X,Y); if(X==1)return {q,1}; bint r=X; int lim=boost::multiprecision::msb(Y)+1; for(int k=1;k>T; while(T--){ bint A,B,C; cin>>A>>B>>C; auto [u,v]=Ratio(A,C); cout<<(B*u/v)%998244353<<'\n'; } }