結果

問題 No.1819 Mirrored 2
コンテスト
ユーザー eQe
提出日時 2026-01-29 16:50:07
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,170 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,574 ms
コンパイル使用メモリ 347,960 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-29 16:50:13
合計ジャッジ時間 5,576 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include<atcoder/modint>
#endif
using namespace std;
#define RD(T,...) T __VA_ARGS__;lin(__VA_ARGS__)
#define LL(...) RD(ll,__VA_ARGS__)
#define FO(n) for(ll IJK=n;IJK-->0;)
#define fo(i,...) for(auto[i,i##stop,i##step]=for_range<ll>(0,__VA_ARGS__);i<i##stop;i+=i##step)
#define of(i,...) for(auto[i,i##stop,i##step]=for_range<ll>(1,__VA_ARGS__);i>=i##stop;i+=i##step)
#define defpp template<ostream&o=cout>void pp(const auto&...a){[[maybe_unused]]const char*c="";((o<<c<<a,c=" "),...);o<<'\n';}void epp(const auto&...a){pp<cerr>(a...);}
#define entry defpp void main();void main2();}int main(){my::io();my::main();}namespace my{
#define use_ml using ml=atcoder::modint;
namespace my{
void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<<fixed<<setprecision(15);}
using ll=long long;
using lll=__int128_t;
using ui32=uint32_t;
using ui64=uint64_t;
template<class T>constexpr auto for_range(T s,T b){T a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};}
void lin(auto&...a){(cin>>...>>a);}
constexpr auto abs(auto x){return x<0?-x:x;}
constexpr ll size2(auto x){x|=1;ll r=0;while(x>0)x>>=1,++r;return r;}
constexpr ll log2_floor(auto x){return size2(x)-1;}
auto ceil(auto x,auto y){if(y<0)x=-x,y=-y;return x<=0?x/y:(x-1)/y+1;}
auto gemin_modulo(auto k,auto r,auto m){r%=m;return ceil(k-r,m)*m+r;}
template<class T,class U>common_type_t<T,U>gcd(T a,U b){return b?gcd(b,a%b):abs(a);}
auto mod(auto a,auto b){return(a%=b)<0?a+b:a;}
auto inv_mod(auto x,auto m){assert(gcd(x,m)==1);decltype(x)a=mod(x,m),b=m,u=1,v=0;while(b)swap(u-=a/b*v,v),swap(a-=a/b*b,b);return mod(u,m);}
auto pow_mod(auto x,auto n,auto m){
  if(n<0)n=-n,x=inv_mod(x,m);
  decltype(x)r=1;
  while(n){
    if(n&1)r=(lll)r*x%m;
    x=(lll)x*x%m;
    n>>=1;
  }
  return r;
}
constexpr ui64 kth_root_floor(ui64 a,ll k){
  if (k==1)return a;
  auto within=[&](ui32 x){ui64 t=1;FO(k)if(__builtin_mul_overflow(t,x,&t))return false;return t<=a;};

  ui64 r=0;
  of(i,sizeof(ui32)*CHAR_BIT)if(within(r|(1u<<i)))r|=1u<<i;
  return r;
}
constexpr auto sqrt_floor(auto x){return kth_root_floor(x,2);}
}
namespace my{
template<class T>T rev10(T x){
  T res=0;
  while(x>0){
    res=res*10+(x%10);
    x/=10;
  }
  return res;
}
}
namespace my{
ll log_mod(ll a,ll b,ll m){
  a=mod(a,m);
  b=mod(b,m);
  if(b==1||m==1)return 0;
  if(a==0)return b==0?1:-1;

  if(gcd(a,m)>1){
    ll d=log2_floor(m);
    ll pwa=1;
    fo(i,d){
      if(pwa==b)return i;
      (pwa*=a)%=m;
    }

    ll g=gcd(pwa,m);
    if(b%g)return-1;

    ll t=log_mod(a,b*inv_mod(pwa,m/g),m/g);
    return t>=0?t+d:-1;

  }else{
    unordered_map<ll,ll>mem;
    ll R=sqrt_floor(m)+1;
    ll pwa=1;
    fo(i,R){
      if(!mem.contains(pwa))mem[pwa]=i;
      (pwa*=a)%=m;
    }

    ll A=pow_mod(inv_mod(a,m),R,m);
    ll t=b;
    fo(i,R){
      if(mem.contains(t))return R*i+mem[t];
      (t*=A)%=m;
    }
    return-1;
  }
}
}
namespace my{entry
void main(){
  LL(P,Q,X,Y);
  use_ml
  ml::set_mod(P);

  ll rM=Y;
  while(mod(rev10(rM),P)==0)rM+=Q;
  ll M=rev10(rM);
  ll k=log_mod(10,M,P);
  ll l=log_mod(10,X,P);
  l=gemin_modulo(k,l,P-1);
  string res=to_string(M)+string(l-k,'0');
  pp(res);
}}
0