QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94722#2172. Trailing Digits8BQube#AC ✓42ms7304kbC++201.2kb2023-04-07 16:32:472023-04-07 16:32:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-07 16:32:50]
  • 评测
  • 测评结果:AC
  • 用时:42ms
  • 内存:7304kb
  • [2023-04-07 16:32:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

int dis[1000005];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    auto cmp = [](string a, string b) {
        if (SZ(a) != SZ(b)) return SZ(a) < SZ(b);  
        return a < b;
    };

    int b, d;
    string a;
    cin >> b >> d >> a;

    auto check = [&](int mid) {
        string s = string(mid, d + '0');
        if (cmp(a, s)) return 0;
        fill(dis, dis + b, -1);
        int x = 0, tn = 1;
        for (int i = 0; i < mid; ++i)
            x = (x * 10 + d) % b, tn = tn * 10 % b;
        int cur = 0, cnt = 0;
        if (d == 0) cur = tn, ++cnt;
        while (dis[cur] == -1)
            dis[cur] = cnt, cur = (cur + tn) % b, ++cnt;
        if (dis[(b - x) % b] == -1) return 0;
        if (dis[(b - x) % b] > 0)
            s = to_string(dis[(b - x) % b]) + s;
        if (cmp(a, s)) return 0;
        return 1;
    };

    int l = 0, r = SZ(a) + 1;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << l << "\n";
}

詳細信息

Test #1:

score: 100
Accepted
time: 19ms
memory: 6580kb

input:

583764 4 558022069184230038938963154373006263760571458771657180531616870174538708073028810782561047069639027608389048778567660978632940168163019291290879822337556840316474756306063761657619759773088336245228734458838815045778851841542788114979050385904301768656279094511344874294029141687083122077500...

output:

9994

result:

ok single line: '9994'

Test #2:

score: 0
Accepted
time: 22ms
memory: 7156kb

input:

583764 2 558022069184230038938963154373006263760571458771657180531616870174538708073028810782561047069639027608389048778567660978632940168163019291290879822337556840316474756306063761657619759773088336245228734458838815045778851841542788114979050385904301768656279094511344874294029141687083122077500...

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 19ms
memory: 6000kb

input:

583764 0 558022069184230038938963154373006263760571458771657180531616870174538708073028810782561047069639027608389048778567660978632940168163019291290879822337556840316474756306063761657619759773088336245228734458838815045778851841542788114979050385904301768656279094511344874294029141687083122077500...

output:

9994

result:

ok single line: '9994'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3352kb

input:

128 2 558022069184230038938963154373006263760571458771657180531616870174538708073028810782561047069639027608389048778567660978632940168163019291290879822337556840316474756306063761657619759773088336245228734458838815045778851841542788114979050385904301768656279094511344874294029141687083122077500733...

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3404kb

input:

128 0 558022069184230038938963154373006263760571458771657180531616870174538708073028810782561047069639027608389048778567660978632940168163019291290879822337556840316474756306063761657619759773088336245228734458838815045778851841542788114979050385904301768656279094511344874294029141687083122077500733...

output:

9999

result:

ok single line: '9999'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

128 8 558022069184230038938963154373006263760571458771657180531616870174538708073028810782561047069639027608389048778567660978632940168163019291290879822337556840316474756306063761657619759773088336245228734458838815045778851841542788114979050385904301768656279094511344874294029141687083122077500733...

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3404kb

input:

3 3 55802206918423003893896315437300626376057145877165718053161687017453870807302881078256104706963902760838904877856766097863294016816301929129087982233755684031647475630606376165761975977308833624522873445883881504577885184154278811497905038590430176865627909451134487429402914168708312207750073308...

output:

10000

result:

ok single line: '10000'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3376kb

input:

2 2 55802206918423003893896315437300626376057145877165718053161687017453870807302881078256104706963902760838904877856766097863294016816301929129087982233755684031647475630606376165761975977308833624522873445883881504577885184154278811497905038590430176865627909451134487429402914168708312207750073308...

output:

10000

result:

ok single line: '10000'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3396kb

input:

1 2 1

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 21ms
memory: 7304kb

input:

999999 1 999999

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 16ms
memory: 7208kb

input:

999999 0 999999

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 41ms
memory: 4764kb

input:

333333 9 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

9996

result:

ok single line: '9996'

Test #14:

score: 0
Accepted
time: 33ms
memory: 5772kb

input:

333333 9 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

9996

result:

ok single line: '9996'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3404kb

input:

44 3 615164488012970354555742215744

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

8 0 9999999999999999999

output:

18

result:

ok single line: '18'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

8 2 9999999999999999999

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3392kb

input:

8 4 9999999999999999999

output:

2

result:

ok single line: '2'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3344kb

input:

8 6 9999999999999999999

output:

1

result:

ok single line: '1'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3308kb

input:

8 8 9999999999999999999

output:

19

result:

ok single line: '19'

Test #21:

score: 0
Accepted
time: 2ms
memory: 4320kb

input:

262144 0 9999999999999999999

output:

18

result:

ok single line: '18'

Test #22:

score: 0
Accepted
time: 2ms
memory: 4416kb

input:

262144 2 9999999999999999999

output:

1

result:

ok single line: '1'

Test #23:

score: 0
Accepted
time: 1ms
memory: 5740kb

input:

262144 4 9999999999999999999

output:

2

result:

ok single line: '2'

Test #24:

score: 0
Accepted
time: 0ms
memory: 4344kb

input:

262144 6 9999999999999999999

output:

1

result:

ok single line: '1'

Test #25:

score: 0
Accepted
time: 3ms
memory: 5668kb

input:

262144 8 9999999999999999999

output:

3

result:

ok single line: '3'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3448kb

input:

625 0 1000

output:

0

result:

ok single line: '0'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

625 0 10000

output:

4

result:

ok single line: '4'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3324kb

input:

625 0 10000000000

output:

10

result:

ok single line: '10'

Test #29:

score: 0
Accepted
time: 2ms
memory: 3304kb

input:

625 5 1000

output:

1

result:

ok single line: '1'

Test #30:

score: 0
Accepted
time: 2ms
memory: 3400kb

input:

625 5 10000

output:

1

result:

ok single line: '1'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3380kb

input:

625 5 10000000000

output:

1

result:

ok single line: '1'

Test #32:

score: 0
Accepted
time: 21ms
memory: 5072kb

input:

416113 2 910206714449570543178771288072

output:

24

result:

ok single line: '24'

Test #33:

score: 0
Accepted
time: 9ms
memory: 5704kb

input:

155727 8 595222817557156175409864490146

output:

24

result:

ok single line: '24'

Test #34:

score: 0
Accepted
time: 1ms
memory: 6240kb

input:

482185 7 175891766468946506850940294915

output:

0

result:

ok single line: '0'

Test #35:

score: 0
Accepted
time: 34ms
memory: 6552kb

input:

809543 9 706310782306606357041238521573

output:

24

result:

ok single line: '24'

Test #36:

score: 0
Accepted
time: 32ms
memory: 6448kb

input:

784349 2 140172854681543411198107462791

output:

23

result:

ok single line: '23'

Test #37:

score: 0
Accepted
time: 42ms
memory: 6736kb

input:

884771 6 878053904682776335641403365951

output:

24

result:

ok single line: '24'

Test #38:

score: 0
Accepted
time: 5ms
memory: 6468kb

input:

285115 7 510637551593904109970235924750

output:

0

result:

ok single line: '0'

Test #39:

score: 0
Accepted
time: 11ms
memory: 5960kb

input:

446344 8 903873563961494937101879656386579063234122909426702463868191198982245137424039427440175427556962397041118420136726887092853026726934104808566629597404508140480575992676594274115233279041150264028795434104067914849478866456192407793002021965833468079778630255143444525376989079382208643362458...

output:

9995

result:

ok single line: '9995'

Test #40:

score: 0
Accepted
time: 7ms
memory: 4252kb

input:

217176 8 746720628343704092031643549114635655136791126811051782038588698583562173486474660147736305824479303770760232163768352183708565173054518463256824577064413625680194290063831377238862971071846843280498770970154459912493995293604486306696113122808160233657375115399216282414502057456592999985641...

output:

9995

result:

ok single line: '9995'

Test #41:

score: 0
Accepted
time: 13ms
memory: 6032kb

input:

591976 8 997688187554288608289696884444974394245886896647212441828767818311997092160967371255532165988508545021286506736704730143980876547206426443074075450563958052385014127642212294228193051916496652316016549674647007259802903947613096796599924760429663473913319454783603356257452483582255380157929...

output:

9995

result:

ok single line: '9995'

Test #42:

score: 0
Accepted
time: 7ms
memory: 4620kb

input:

308945 5 962476931095598250044305868135885243557388313522332291867917574431355233922993304117647070995131553330332941633745363521615864814876653718068119371777377239796738753166939860072333764723729655459600360732826690810931322099300456303655259230988921806364953099639264334432713159446169102673437...

output:

9995

result:

ok single line: '9995'

Test #43:

score: 0
Accepted
time: 25ms
memory: 7208kb

input:

953215 5 481379773305937010787000848653505393811784682453377327931890614700475555426776917124183304939480619234810630040231631970261984136707831904841144438858481007543348015107439662369399747861912671557090065865016622444295889867974657697201792908751777382148402012154785104292434498920894247193558...

output:

9994

result:

ok single line: '9994'

Test #44:

score: 0
Accepted
time: 19ms
memory: 6252kb

input:

711785 5 624522418749983727962202416596678244083668011938141912561864354048413105915711234753191969044814346136404671485469428764114784402574391892322067753961421343947532626292641042989488918633658784104942163903053502260790194000740256301403470440332255977429369236483168636332974165475448631524588...

output:

9994

result:

ok single line: '9994'