結果
| 問題 | No.3186 Big Order |
| コンテスト | |
| ユーザー |
C
|
| 提出日時 | 2026-11-18 16:29:53 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 2 ms / 2,000 ms |
| + 205µs | |
| コード長 | 4,631 bytes |
| 記録 | |
| コンパイル時間 | 13,429 ms |
| コンパイル使用メモリ | 708,068 KB |
| 実行使用メモリ | 9,908 KB |
| 最終ジャッジ日時 | 2026-11-18 16:30:13 |
| 合計ジャッジ時間 | 16,568 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 37 |
ソースコード
#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 <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <atcoder/all>
#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<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;
// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;
// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
using vvm=vector<vm>;
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<Y が成立する。X=1 なら残りの比は 0。
*
* 3. Euclid式再帰
* ここから 1<X<Y, X|Y とし、theta=rho(X,Y)<1 を求める
* Y \nmid X^k を満たす正整数 k を選び
*
* h = gcd(X^k,Y), Y' = Y/h
*
* とする。このとき、次の重要な恒等式が成立する
*
* rho(X,Y') = theta/(1-k*theta)
*
* 証明 :p|Y に対して a=v_p(X), c=v_p(Y) とおくと
*
* v_p(Y') = c-min(k*a,c) = max(c-k*a,0)
*
* したがって Y' に残る素数は a/c<1/k を満たし、その指数比は
*
* a/c -> 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<lim;k*=2){
bint s=r*r%Y;
if(s==0){
auto [u,v]=Ratio(X,Y/boost::multiprecision::gcd(r,Y));
v+=k*u;
u+=q*v;
return {u,v};
}
r=s;
}
return {q,1};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
bint A,B,C;
cin>>A>>B>>C;
auto [u,v]=Ratio(A,C);
cout<<(B*u/v)%998244353<<'\n';
}
}
C