QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94722 | #2172. Trailing Digits | 8BQube# | AC ✓ | 42ms | 7304kb | C++20 | 1.2kb | 2023-04-07 16:32:47 | 2023-04-07 16:32:50 |
Judging History
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'