結果
| 問題 |
No.3186 Big Order
|
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2025-06-21 01:50:38 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 19,905 bytes |
| コンパイル時間 | 3,292 ms |
| コンパイル使用メモリ | 233,648 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-06-21 01:50:50 |
| 合計ジャッジ時間 | 11,766 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 13 TLE * 1 -- * 20 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//bigint用のNTT 268行目まで.
const long long mod = 998244353;
//入力が必ずmod未満の時に使う.
struct mint{
long long v = 0;
mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;}
long long val(){return v;}
void modu(){v %= mod;}
mint repeat2mint(const long long a,long long b){
mint ret = 1,p = a;
while(b){
if(b&1) ret *= p;
p *= p; b >>= 1;
}
return ret;
};
mint operator+(const mint b){return mint(v)+=b;}
mint operator-(const mint b){return mint(v)-=b;}
mint operator*(const mint b){return mint(v)*=b;}
mint operator/(const mint b){return mint(v)/=b;}
mint operator+=(const mint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
mint operator-=(const mint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
mint operator*=(const mint b){v = v*b.v%mod; return *this;}
mint operator/=(mint b){
if(b == 0) assert(false);
int left = mod-2;
while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
return *this;
}
mint operator++(int){*this += 1; return *this;}
mint operator--(int){*this -= 1; return *this;}
bool operator==(const mint b){return v == b.v;}
bool operator!=(const mint b){return v != b.v;}
bool operator>(const mint b){return v > b.v;}
bool operator>=(const mint b){return v >= b.v;}
bool operator<(const mint b){return v < b.v;}
bool operator<=(const mint b){return v <= b.v;}
mint pow(const long long x){return repeat2mint(v,x);}
mint inv(){return mint(1)/v;}
};
namespace to_fold{ //纏めて折り畳むためのやつ 苦労したが結局ほぼACLの写経.
__int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;}
pair<long long,long long> invgcd(long long a,long long b){
//return {gcd(a,b),x} (xa≡g(mod b))
a = safemod(a,b);
if(a == 0) return {b,0};
long long x = 0,y = 1,memob = b;
while(a){
long long q = b/a;
b -= a*q;
swap(x,y); y -= q*x;
swap(a,b);
}
if(x < 0) x += memob/b;
return {b,x};
}
long long Garner(vector<long long> &A,vector<long long> &M){
__int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須.
for(int i=1; i<A.size(); i++){
//assert(gcd(mulM,M.at(i-1)) == 1);
mulM *= M.at(i-1); //2乗がオーバーフローする時__int128_t
long long t = safemod((A.at(i)-x)*invgcd(mulM,M.at(i)).second,M.at(i));
x += t*mulM;
}
return x%mod;
}
int countzero(unsigned long long x){
if(x == 0) return 64;
else return __popcount((x&-x)-1);
}
constexpr int countzero2(int x){
int ret = 0;
while(!(x&(1<<ret))) ret++;
return ret;
}
struct fftinfo{
static constexpr int rank2 = countzero2(mod-1);
array<mint,rank2+1> root,iroot;
array<mint,max(0,rank2-2+1)> rate2,irate2;
array<mint,max(0,rank2-3+1)> rate3,irate3;
fftinfo(mint g){
root[rank2] = g.pow((mod-1)>>rank2);
iroot[rank2] = root[rank2].inv();
for(int i=rank2-1; i>=0; i--){
root[i] = root[i+1]*root[i+1];
iroot[i] = iroot[i+1]*iroot[i+1];
}
mint mul = 1,imul = 1;
for(int i=0; i<=rank2-2; i++){
rate2[i] = root[i+2]*mul;
irate2[i] = iroot[i+2]*imul;
mul *= iroot[i+2],imul *= root[i+2];
}
mul = 1,imul = 1;
for(int i=0; i<=rank2-3; i++){
rate3.at(i) = root[i+3]*mul;
irate3.at(i) = iroot[i+3]*imul;
mul *= iroot[i+3],imul *= root[i+3];
}
}
};
mint findroot(){
if(mod == 998244353) return mint(3);
else if(mod == 754974721) return mint(11);
else if(mod == 167772161) return mint(3);
else if(mod == 469762049) return mint(3);
long long p = mod-1;
vector<long long> P;
for(long long i=2; i*i<=p; i++){
if(p%i) continue;
while(p%i == 0) p /= i;
P.push_back(i);
}
if(p != 1) P.push_back(p);
p = mod-1;
random_device rnd; mt19937 mt(rnd());
while(true){
mint ret = mt()%mod;
if(ret == 1 || ret == 0) continue;
if(ret.pow(p) != 1) continue;
bool ok = true;
for(auto check : P) if(ret.pow(p/check) == 1){ok = false; break;}
if(ok) return ret;
} //O(√P)らしいです.
}
void NTT(vector<mint> &A,fftinfo &info){
int N = A.size(),ln = countzero(N);
int dep = 0;
while(dep < ln){
if(ln-dep == 1){
int p = 1<<(ln-dep-1);
mint rot = 1;
for(int o=0; o<(1<<dep); o++){
int offset = o<<(ln-dep);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;
A.at(i+offset) = l+r; A.at(i+offset+p) = l-r;
}
if(o+1 != (1<<dep)) rot *= info.rate2[countzero(~(unsigned int)o)];
}
dep++;
}
else{
int p = 1<<(ln-dep-2);
mint rot = 1,imag = info.root[2];
for(int o=0; o<(1<<dep); o++){
mint rot2 = rot*rot,rot3 = rot2*rot;
int offset = o<<(ln-dep);
for(int i=0; i<p; i++){
auto mod2 = 1ULL*mod*mod;
auto a0 = 1ULL*A.at(i+offset).v;
auto a1 = 1ULL*A.at(i+offset+p).v*rot.v;
auto a2 = 1ULL*A.at(i+offset+p+p).v*rot2.v;
auto a3 = 1ULL*A.at(i+offset+p+p+p).v*rot3.v;
auto a1m2a3im = 1ULL*(a1+mod2-a3+mod)%mod*imag.v;
auto m2a2 = mod2-a2;
A.at(i+offset) = (long long)((a0+a2+a1+a3)%mod);
A.at(i+offset+p) = (long long)((a0+a2+(2*mod2-(a1+a3)))%mod);
A.at(i+offset+p+p) = (long long)((a0+m2a2+a1m2a3im)%mod);
A.at(i+offset+p+p+p) = (long long)((a0+m2a2+(mod2-a1m2a3im))%mod);
}
if(o+1 != (1<<dep)) rot *= info.rate3[countzero(~(unsigned int)o)];
}
dep += 2;
}
}
}
void INTT(vector<mint> &A,fftinfo &info){
int N = A.size(),ln = countzero(N);
int dep = ln;
while(dep){
if(dep == 1){
int p = 1<<(ln-dep);
mint irot = 1;
for(int o=0; o<(1<<(dep-1)); o++){
int offset = o<<(ln-dep+1);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p);
A.at(i+offset) = l+r;
A.at(i+offset+p) = (long long)((unsigned long long)((mod+l.v-r.v)*irot.v)%mod);
}
if(o+1 != (1<<(dep-1))) irot *= info.irate2[countzero(~(unsigned int)o)];
}
dep--;
}
else{
int p = 1<<(ln-dep);
mint irot = 1,iimag = info.iroot[2];
for(int o=0; o<(1<<(dep-2)); o++){
mint irot2 = irot*irot,irot3 = irot2*irot;
int offset = o<<(ln-dep+2);
for(int i=0; i<p; i++){
auto a0 = 1ULL*A.at(i+offset).v,a1 = 1ULL*A.at(i+offset+p).v;
auto a2 = 1ULL*A.at(i+offset+p+p).v,a3 = 1ULL*A.at(i+offset+p+p+p).v;
auto gotyagotya = 1ULL*((mod+a2-a3)*iimag.v%mod);
A.at(i+offset) = (long long)((a0+a1+a2+a3)%mod);
A.at(i+offset+p) = (long long)((a0+(mod-a1)+gotyagotya)*irot.v%mod);
A.at(i+offset+p+p) = (long long)((a0+a1+(mod-a2)+(mod-a3))*irot2.v%mod);
A.at(i+offset+p+p+p) = (long long)((a0+(mod-a1)+(mod-gotyagotya))*irot3.v%mod);
}
if(o+1 != (1<<(dep-2))) irot *= info.irate3[countzero(~(unsigned int)o)];
}
dep -= 2;
}
}
}
vector<mint> convolutionnaive(vector<mint> &A,vector<mint> &B){
vector<mint> ret(A.size()+B.size()-1);
for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);
return ret;
}
vector<mint> convolution(vector<mint> &A,vector<mint> &B){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;
if(siza == 0 || sizb == 0) return {};
while(N <= sizc) N <<= 1;
vector<mint> ca = A,cb = B;
ca.resize(N),cb.resize(N);
if(min(siza,sizb) <= 40) return convolutionnaive(A,B);
assert((mod-1)%N == 0);
mint root = findroot();
fftinfo info(root);
NTT(ca,info); NTT(cb,info);
for(int i=0; i<N; i++) ca.at(i) *= cb.at(i);
INTT(ca,info); ca.resize(sizc);
mint divN = mint(N).inv();
for(int i=0; i<sizc; i++) ca.at(i) *= divN;
return ca;
}
vector<int> convolution_int(vector<int> &A,vector<int> B){
if(A.size() == 0 || B.size() == 0) return {};
vector<int> ret;
if(min(A.size(),B.size()) <= 40){
ret.resize(A.size()+B.size()-1);
for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);
}
else{
vector<mint> X,Y,Z;
for(auto &a : A) X.push_back(a);
for(auto &b : B) Y.push_back(b);
Z = convolution(X,Y);
for(auto &z : Z) ret.push_back(z.v);
}
return ret;
}
}
using namespace to_fold;
struct bigint{
//__int128_t以上の数にも対応.
//計算量 普通O(桁数),掛け算O(桁数log桁数),割り算O(桁数log桁数)(重い).
public:
bool isMinus; //負かどうか.
vector<int> V;//絶対値.
//先頭の要素の方が小さい位 5108->{8,0,1,5}.
private:
void slide(){
for(int i=0; i<V.size(); i++){
int v = V.at(i);
int div10 = v<0?(v+1)/10-1:v/10; //÷10切り捨て.
if(div10 == 0) continue;
if(i+1==V.size()) V.push_back(0);
V.at(i+1) += div10; V.at(i) -= div10*10;
}
while(V.size() && V.back() == 0) V.pop_back();
if(V.size() == 0) isMinus = false;
}
int comp(const bigint &b){ //0->|a|<|b|,1->|a|>|b|,2->|a|==|b|.
if(V.size() < b.V.size()) return 0;
if(V.size() > b.V.size()) return 1;
for(int i=V.size(); i--;){
if(V.at(i) == b.V.at(i)) continue;
return V.at(i)>b.V.at(i);
}
return 2;
}
public:
bigint():isMinus(false),V({}){}
template<typename T>
bigint(T a){
if(a < 0) isMinus = true,a = -a;
else isMinus = false;
V = {};
while(a) V.push_back(a%10),a /= 10;
}
bigint(const string &s){
V = {};
if(s.size() == 0) isMinus = false;
else{
if(s.at(0) == '-') isMinus = true;
else isMinus = false;
for(int i=s.size(); i--;) V.push_back(s.at(i)-'0');
if(isMinus) V.pop_back();
while(V.size() && V.back() == '0') V.pop_back();
}
}
bigint(const bigint &n){isMinus = n.isMinus; V = n.V;}
bigint &operator=(const bigint &b) = default;
bigint operator+(const bigint &b){
bigint ret;
if(isMinus == b.isMinus){
ret = *this;
ret.V.resize(max(V.size(),b.V.size()));
for(int i=0; i<b.V.size(); i++) ret.V.at(i) += b.V.at(i);
}
else{
int now = comp(b);
if(now == 2) return bigint(0);
if(now == 1){
ret = *this;
for(int i=0; i<b.V.size(); i++) ret.V.at(i) -= b.V.at(i);
}
else{
ret = b;
for(int i=0; i<V.size(); i++) ret.V.at(i) -= V.at(i);
}
}
ret.slide(); return ret;
}
bigint operator-(const bigint &b){
bigint ret;
if(isMinus != b.isMinus){
ret = *this;
ret.V.resize(max(V.size(),b.V.size()));
for(int i=0; i<b.V.size(); i++) ret.V.at(i) += b.V.at(i);
}
else{
int now = comp(b);
if(now == 2) return bigint(0);
if(now == 1){
ret = *this;
for(int i=0; i<b.V.size(); i++) ret.V.at(i) -= b.V.at(i);
}
else{
ret = b; ret.isMinus ^= 1;
for(int i=0; i<V.size(); i++) ret.V.at(i) -= V.at(i);
}
}
ret.slide(); return ret;
}
bigint operator*(const bigint &b){
bigint ret; ret.isMinus = (isMinus^b.isMinus);
ret.V = convolution_int(V,b.V);
ret.slide(); return ret;
}
bigint operator/(const bigint &b){//b!=0.
assert(b.V.size());
bigint ret(0); ret.isMinus = isMinus^b.isMinus;
if(bigint(1) == b) return (*this);
if(b.V.size() < 64){
auto a = *this;
int n = (*this).V.size(),m = b.V.size();
for(int i=n-1; i>=0; i--){
int ok = 0;
bigint now;
for(int k=i; k<min(n,i+m+1); k++) now.V.push_back(a.V.at(k));
int memo = now.size();
while(now.V.size() && now.V.back() == 0) now.V.pop_back();
for(int v=1; v<10; v++){
if(now >= b) now -= b,ok++;
else break;
}
now.V.resize(memo);
for(int k=i; k<min(n,i+m+1); k++) a.V.at(k) = now.V.at(k-i);
ret.V.push_back(ok);
}
reverse(ret.V.begin(),ret.V.end());
while(ret.V.size() && ret.V.back() == 0) ret.V.pop_back();
return ret;
}
//ニュートン法.
int accu = 2,need = max(2,(int)V.size()-(int)b.V.size()+2);
bigint invB(10),two(200);
for(int i=0; i<6; i++){ //精度2桁までやる
bigint one = invB*b;
two.V.pop_back();
while(two.V.size() < one.V.size()) two.V.push_back(0);
while(two.V.size() > one.V.size()) two.V.pop_back();
two.V.push_back(2);
bigint next = invB*(two-one);
invB.V.assign(2,0);
invB.V.at(1) = next.V.back(); next.V.pop_back();
invB.V.at(0) = next.V.back();
}
while(accu < need){ //精度倍々になる.
bigint one = invB*b;
two.V.pop_back();
while(two.V.size() < one.V.size()) two.V.push_back(0);
two.V.push_back(2);
bigint next = invB*(two-one);
accu = min(accu<<1,need);
invB.V.clear();
for(int i=max(0,(int)next.V.size()-accu); i<next.V.size(); i++) invB.V.push_back(next.V.at(i));
}
{ //精度足りてない場合があるのでラスト1回.
bigint one = invB*b;
two.V.pop_back();
while(two.V.size() < one.V.size()) two.V.push_back(0);
two.V.push_back(2);
bigint next = invB*(two-one);
accu = min(accu<<1,need);
invB.V.clear();
for(int i=max(0,(int)next.V.size()-accu); i<next.V.size(); i++) invB.V.push_back(next.V.at(i));
}
bigint check = (*this)*invB; //floor(check)=ret.
for(int i=invB.V.size()+b.V.size()-1; i<check.V.size(); i++) ret.V.push_back(check.V.at(i));
if((*this)-ret*b >= b){ //+1の可能性.
int digit = 0;
ret.V.push_back(0);
ret.V.at(digit)++;
while(ret.V.at(digit) == 10) ret.V.at(digit) = 0,ret.V.at(++digit)++;
if(ret.V.back() == 0) ret.V.pop_back();
}
return ret;
}
bigint operator%(const bigint &b){ //a>=0,b>0を仮定.
bigint ret = *this;
ret -= ret/b*b;
return ret;
}
bigint operator+=(const bigint &b){return *this=*this+b;}
bigint operator-=(const bigint &b){return *this=*this-b;}
bigint operator*=(const bigint &b){return *this=*this*b;}
bigint operator/=(const bigint &b){return *this=*this/b;}
bigint operator%=(const bigint &b){return *this=*this%b;}
bool operator==(const bigint &b){
if(V.size() != b.V.size() || isMinus != b.isMinus) return false;
return V == b.V;
}
bool operator<(const bigint &b){
if(isMinus && !b.isMinus) return true;
if(!isMinus && b.isMinus) return false;
if(!isMinus && !b.isMinus){
if(V.size() < b.V.size()) return true;
if(V.size() > b.V.size()) return false;
for(int i=V.size(); i--;){
if(V.at(i) == b.V.at(i)) continue;
return V.at(i) < b.V.at(i);
}
return false;
}
else{
if(V.size() > b.V.size()) return true;
if(V.size() < b.V.size()) return false;
for(int i=V.size(); i--;){
if(V.at(i) == b.V.at(i)) continue;
return V.at(i) > b.V.at(i);
}
return false;
}
}
bool operator<=(const bigint &b){
if(isMinus && !b.isMinus) return true;
if(!isMinus && b.isMinus) return false;
if(!isMinus && !b.isMinus){
if(V.size() < b.V.size()) return true;
if(V.size() > b.V.size()) return false;
for(int i=V.size(); i--;){
if(V.at(i) == b.V.at(i)) continue;
return V.at(i) < b.V.at(i);
}
return true;
}
else{
if(V.size() > b.V.size()) return true;
if(V.size() < b.V.size()) return false;
for(int i=V.size(); i--;){
if(V.at(i) == b.V.at(i)) continue;
return V.at(i) > b.V.at(i);
}
return true;
}
}
bool operator>(const bigint &b){return !(*this<=b);}
bool operator>=(const bigint &b){return !(*this<b);}
bool operator!=(const bigint &b){return !(*this==b);}
unsigned int size(){return V.size();}
mint get(){
mint ret = 0,p10 = 1;
for(auto v : V) ret += p10*v,p10 *= 10;
return ret;
}
};
istream &operator>>(istream &is,bigint &a){
string s; cin >> s;
a = bigint(s);
return is;
}
ostream &operator<<(ostream &os,bigint a){
if(a.isMinus) cout << "-";
if(a.V.size() == 0) cout << 0;
for(int i=a.V.size(); i--;) cout << a.V.at(i);
return os;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
int Need = 30000;
vector<int> allp;
vector<bool> prime(Need+1,true);
prime.at(0) = false; prime.at(1) = false;
for(int i=2; i<=Need; i++){
if(!prime.at(i)) continue;
allp.push_back(i);
for(long long k=((long long)i)*i; k<=Need; k+=i) prime.at(k) = false;
}
while(T--){
bigint a,b,c; cin >> a >> b >> c;
mint answer = 0;
while(a%c == 0) answer += b.get(),a /= c;
pair<int,int> worst = {1,1};
auto chmin = [&](pair<int,int> check){if(worst.first*check.second > worst.second*check.first) worst = check;};
for(auto p : allp){
int one = 0,two = 0;
while(a%p == 0) a /= p,one++;
while(c%p == 0) c /= p,two++;
if(two == 0) continue;
chmin({one,two});
if(one == 0) break;
}
if(worst.first != 0 && c != 1){
int n = 840,ok = 0;
bigint a2 = 1;
while(n){
if(n&1) a2 *= a;
a *= a,n >>= 1;
}
while(a2%c == 0) a2 /= c,ok++;
n = 840;
chmin({ok,n});
}
bigint b2 = b/worst.second*worst.first;
int bint = (b%worst.second).get().v;
answer += b2.get();
for(int i=1; ; i++){
if(i*worst.second <= bint*worst.first) answer++;
else break;
}
cout << answer.v << "\n";
}
}