提出 #69350415

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define fileio(x,y) freopen(x,"r",stdin),freopen(y,"w",stdout)
#define tup tuple<int,int,int>
#define fir(x) (get<0>(x))
#define sec(x) (get<1>(x))
#define thr(x) (get<2>(x))
#define pii pair<int,int>
#define bit(x) bitset<x>
#define pb emplace_back
#define i12 __int128_t
#define mt make_tuple
#define mp make_pair

const int	mod=998244353;
const int	maxn=2e5+10;

string  s;
int     p[maxn];
int     n,k,ttt;

// ax+by = 1
int exgcd(int x,int y,int &a,int &b) { if(!y) return a=1,b=0,x; int t=exgcd(y,x%y,a,b); b=a-x/y*(a=b); return t; }

string getstr(tup x)
{
    int xl=fir(x),xr=sec(x),xn=thr(x),xln=to_string(xr).size();
    string xx=(xl? to_string(xl):"")+s; for(int i=0; i<xn-xln; i++) xx+='0'; xx+=(xn? to_string(xr):"");
    return xx;
}

bool cmp(tup x,tup y)
{
    // cerr<<fir(x)<<' '<<sec(x)<<' '<<thr(x)<<'\n';
    int xl=fir(x),xn=thr(x),xln=to_string(xl).size()-(!xl),xtot=xln+n+xn;
    int yl=fir(y),yn=thr(y),yln=to_string(yl).size()-(!yl),ytot=yln+n+yn;
    if(xtot!=ytot) return xtot<ytot;
    return getstr(x)<getstr(y);
}

void work()
{
    /* Code */
    ttt=0;
    cin>>k>>s; int val=0; n=s.size();
    int x=0,kk=k; while(kk) x++,kk/=10;
    int p10s=1; tup tar(1e8,1e8,11);
    for(int i=0; i<n; i++) val=(val*10+s[i]-'0')%k,p10s=p10s*10%k;
    for(int r=0,rval=val; r<=x/2; r++,rval=rval*10%k)
    {
        for(int rv=0; rv<p[r]; rv++)
        {
            int v=(rval+rv)%k;
            int lbase=p10s*(p[r]%k)%k;
            // calc min x -> x*lbase + v = 0 (mod k)
            // x*lbase + pk = k - v
            // cerr<<r<<' '<<rv<<' '<<p10s<<' '<<lbase<<' '<<val<<' '<<v<<' '<<k<<'\n';
            tup res;
            // if(v)
            {
                // 10x+15p=10 -> 2x+3p=2
                int x,p; int g=exgcd(lbase,k,x,p);
                if((k-v)%g) continue;
                int c=(k-v)/g; x*=c;
                // cerr<<x<<' '<<p*c<<'\n';
                int kk=k/g,minx=x%kk+kk*(x%kk<0);
                res=mt(minx,rv,r);
            }
            // else res=mt(0,rv,r);
            if(cmp(res,tar)) tar=res;
        }
    }
    int rval=val*(p[x-x/2]%k)%k;
    for(int l=x/2; l>=0; l--,rval=rval*10%k)
    {
        int r=x-l;
        for(int lv=0; lv<p[l]; lv++)
        {
            int v=lv%k*p10s%k*p[r]%k;
            (v+=rval)%=k;
            // calc min x -> x + v = 0 (mod k)
            int x=k-v;
            if(x>=p[r]) continue;
            if(cmp(mt(lv,x,r),tar)) tar=mt(lv,x,r);
        }
    }
    // cerr<<fir(tar)<<' '<<sec(tar)<<' '<<thr(tar)<<'\n';
    cout<<getstr(tar)<<'\n';
    return;
}

signed main()
{
    // fileio(".in",".out");
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t,stTime=clock();
    cin>>t;
    p[0]=1; for(int i=1; i<=18; i++) p[i]=p[i-1]*10;
    while(t--) work();
    // cerr<<"Time : "<<(double)(clock()-stTime)/CLOCKS_PER_SEC<<'\n';
    return 0;
} // Cellinia Texas.

提出情報

コンパイルエラー

Main.cpp: In function ‘long long int exgcd(long long int, long long int, long long int&, long long int&)’:
Main.cpp:27:99: warning: operation on ‘a’ may be undefined [-Wsequence-point]
   27 | int exgcd(int x,int y,int &a,int &b) { if(!y) return a=1,b=0,x; int t=exgcd(y,x%y,a,b); b=a-x/y*(a=b); return t; }
      |                                                                                                 ~~^~~
Main.cpp: In function ‘int main()’:
Main.cpp:101:11: warning: unused variable ‘stTime’ [-Wunused-variable]
  101 |     int t,stTime=clock();
      |           ^~~~~~

ジャッジ結果