#1198497 (C++23(gcc16)) No.3186 Big Order

• 問題: No.3186 Big Order
• ユーザー: C
• 提出日時: 2026-11-13 01:44:06
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 229 ms / 2,000 ms
• コード長: 3,913 bytes
• コンパイル時間: 13,682 ms
• コンパイル使用メモリ: 687,452 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-11-13 01:44:26
• 合計ジャッジ時間: 17,140 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge5_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 <boost/multiprecision/integer.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 boost::multiprecision::cpp_int;
const ll MOD=998244353;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

	/**
	 * O(log A + log C) 回の多倍長整数演算　
	 * （L = log A + log C とすると、ビット計算量は O(L^4)、FFTなどを使えば O(L^3polylogL)）
	 * 
	 * C^k | A^n となる最大の非負整数 k を f(n) とする。
	 * また、素数 p に対して A, C に含まれる p の指数をそれぞれ a_p, c_p とする。
	 *
	 * 素因数分解を考えると
	 * C^k | A^n <=> すべての p | C について k*c_p <= n*a_p。
	 *
	 * この「すべての p」という条件を一つの閾値にまとめるため
	 * \alpha = min_{p|C} (a_p/c_p) とおくと
	 * C^k | A^n <=> k <= n\alpha、すなわち f(n) = floor(n\alpha)
	 * よって \alpha さえ求まれば、答えは f(B) = floor(B*\alpha) となる。
	 *
	 * しかし、\alpha を直接求めるには C の素因数分解が必要で、これは難しい
	 * そこで、\alpha を別の方法で求められないか考える。
	 *
	 * f(n)/n <= \alpha なので、ある n で = が成立すれば、
	 * \alpha を f(n)/n の最大値として求められるのではないか？
	 *
	 * \alpha = a_p/c_p を達成する素数 p | C を一つ取る
	 * n = c_p とすると f(n) = a_p なので、f(n)/n = \alpha が成立する！
	 * さらに、2^c_p <= C より c_p <= floor(log_2 C)。
	 *
	 * したがって M = floor(log_2 C) とおけば
	 * \alpha = max_{1<=n<=M} f(n)/n
	 * M は高々 132 なので、f(1), ..., f(M) を求めれば良い。
	 *
	 * では、これらをどう計算するか？
	 * R_n = A^n / C^{f(n)} とおくと、R_n は C で割り切れない整数
	 * 初期値は R_0 = 1, f(0) = 0
	 * R_{n-1} に A を掛け、C で割れる限り割り続ければ、
	 * R_n と f(n) が同時に求まる。
	 * つまり、非常に素朴なシミュレーションで全て計算できる。
	 *
	 * この繰り返し除算は一見重そうだが、償却解析できる
	 * n 回目の成功した除算回数は f(n)-f(n-1) なので、
	 * 全体では f(M) 回しか成功しない。
	 * C^{f(M)} <= A^M かつ M <= log_2 C より、
	 * f(M) <= log_2 A
	 * 失敗する割り切り判定も各 n につき高々 1 回。
	 *
	 * よって O(log A + log C) 回の多倍長整数演算で \alpha が求まる
	 * 中間整数のビット長は O(log A * log C)ですが
	 */

	int T;
	cin>>T;
	while(T--){
		cpp_int A,C;
		string B;
		cin>>A>>B>>C;
		int M=boost::multiprecision::msb(C);//floor(log_2C)
		cpp_int R=1;
		int f=0,u=0,v=1;//最終的に\alpha = u/v
		for(int n=1;n<=M;n++){
			R*=A;
			while(R%C==0){
				R/=C;
				f++;
			}
			if(f*v>u*n){
				u=f;
				v=n;
			}
		}
		auto decimal_mod=[](const string&S,ll mod){
			ll r=0;
			each(c,S)r=(r*10+c-'0')%mod;
			return r;
		};
		ll r=decimal_mod(B,MOD*v);
		cout<<(r*u/v)%MOD<<'\n';
	}
}