| Task: | A TIMES B! |
| Sender: | aalto26hw_006 |
| Submission time: | 2026-10-28 17:16:22 +0200 |
| Language: | C++ (C++23) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | ACCEPTED | 0.00 s | details |
| #3 | ACCEPTED | 0.01 s | details |
| #4 | ACCEPTED | 0.00 s | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | ACCEPTED | 0.00 s | details |
| #7 | ACCEPTED | 0.00 s | details |
| #8 | ACCEPTED | 0.00 s | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | ACCEPTED | 0.00 s | details |
| #11 | ACCEPTED | 0.00 s | details |
| #12 | ACCEPTED | 0.00 s | details |
| #13 | ACCEPTED | 0.00 s | details |
| #14 | ACCEPTED | 0.00 s | details |
| #15 | ACCEPTED | 0.00 s | details |
| #16 | ACCEPTED | 0.00 s | details |
| #17 | ACCEPTED | 0.00 s | details |
| #18 | ACCEPTED | 0.00 s | details |
| #19 | ACCEPTED | 0.00 s | details |
| #20 | ACCEPTED | 0.00 s | details |
| #21 | ACCEPTED | 0.00 s | details |
| #22 | ACCEPTED | 0.00 s | details |
| #23 | ACCEPTED | 0.00 s | details |
| #24 | ACCEPTED | 0.00 s | details |
| #25 | ACCEPTED | 0.00 s | details |
| #26 | ACCEPTED | 0.00 s | details |
| #27 | ACCEPTED | 0.00 s | details |
| #28 | ACCEPTED | 0.00 s | details |
| #29 | ACCEPTED | 0.00 s | details |
| #30 | ACCEPTED | 0.00 s | details |
| #31 | ACCEPTED | 0.00 s | details |
| #32 | ACCEPTED | 0.00 s | details |
| #33 | ACCEPTED | 0.00 s | details |
| #34 | ACCEPTED | 0.00 s | details |
| #35 | ACCEPTED | 0.00 s | details |
| #36 | ACCEPTED | 0.00 s | details |
| #37 | ACCEPTED | 0.00 s | details |
| #38 | ACCEPTED | 0.00 s | details |
| #39 | ACCEPTED | 0.00 s | details |
| #40 | ACCEPTED | 0.00 s | details |
| #41 | ACCEPTED | 0.00 s | details |
| #42 | ACCEPTED | 0.00 s | details |
| #43 | ACCEPTED | 0.00 s | details |
| #44 | ACCEPTED | 0.00 s | details |
| #45 | ACCEPTED | 0.00 s | details |
| #46 | ACCEPTED | 0.00 s | details |
| #47 | ACCEPTED | 0.00 s | details |
| #48 | ACCEPTED | 0.00 s | details |
| #49 | ACCEPTED | 0.00 s | details |
| #50 | ACCEPTED | 0.00 s | details |
| #51 | ACCEPTED | 0.00 s | details |
| #52 | ACCEPTED | 0.00 s | details |
| #53 | ACCEPTED | 0.00 s | details |
| #54 | ACCEPTED | 0.00 s | details |
| #55 | ACCEPTED | 0.00 s | details |
| #56 | ACCEPTED | 0.07 s | details |
| #57 | ACCEPTED | 0.07 s | details |
| #58 | ACCEPTED | 0.07 s | details |
| #59 | ACCEPTED | 0.07 s | details |
| #60 | ACCEPTED | 0.04 s | details |
| #61 | ACCEPTED | 0.64 s | details |
| #62 | ACCEPTED | 0.65 s | details |
| #63 | ACCEPTED | 0.65 s | details |
| #64 | ACCEPTED | 0.31 s | details |
| #65 | ACCEPTED | 0.63 s | details |
Code
// #ifdef ONLINE_JUDGE
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #endif
#include "bits/stdc++.h"
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fill(arr,val) memset(arr,val,sizeof(arr))
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define dq deque<int>
#define nend '\n'
using namespace std;
const ll inf = 1e18;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
const int MOD = 1e9 + 7;
const ll hashi = 2e9 + 11;
void init_code() {
fast;
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
}
// ---------------- FFT (cp-algorithms template) ----------------
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<cd> & a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j)
swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd & x : a)
x /= n;
}
}
vector<ll> multiply(vector<int> const& a, vector<int> const& b) {
vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < (int)(a.size() + b.size()))
n <<= 1;
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++)
fa[i] *= fb[i];
fft(fa, true);
vector<ll> result(n);
for (int i = 0; i < n; i++)
result[i] = llround(fa[i].real());
return result;
}
// --------------------------------------------------------------
void solve() {
string s, t;
cin >> s >> t;
// digits, lowest first: "123" -> {3,2,1}
vector<int> a(s.size()), b(t.size());
FOR(i,0,(int)s.size()-1) a[i]=s[s.size()-1-i]-'0';
FOR(i,0,(int)t.size()-1) b[i]=t[t.size()-1-i]-'0';
vector<ll> c=multiply(a,b);
// carry: c[k] can be up to 81*1e6, push the overflow to the next digit
string res;
ll carry=0;
for (ll x:c) { x+=carry; res+=char('0'+x%10); carry=x/10; }
while (carry) { res+=char('0'+carry%10); carry/=10; }
while (res.size()>1 && res.back()=='0') res.pop_back();
reverse(ALL(res));
cout << res << nend;
}
int main() {
init_code();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Test details
Test 1
Verdict: ACCEPTED
| input |
|---|
| 8 5 |
| correct output |
|---|
| 40 |
| user output |
|---|
| 40 |
Test 2
Verdict: ACCEPTED
| input |
|---|
| 9 1 |
| correct output |
|---|
| 9 |
| user output |
|---|
| 9 |
Test 3
Verdict: ACCEPTED
| input |
|---|
| 9 5 |
| correct output |
|---|
| 45 |
| user output |
|---|
| 45 |
Test 4
Verdict: ACCEPTED
| input |
|---|
| 2 5 |
| correct output |
|---|
| 10 |
| user output |
|---|
| 10 |
Test 5
Verdict: ACCEPTED
| input |
|---|
| 8 7 |
| correct output |
|---|
| 56 |
| user output |
|---|
| 56 |
Test 6
Verdict: ACCEPTED
| input |
|---|
| 48 92 |
| correct output |
|---|
| 4416 |
| user output |
|---|
| 4416 |
Test 7
Verdict: ACCEPTED
| input |
|---|
| 1 40 |
| correct output |
|---|
| 40 |
| user output |
|---|
| 40 |
Test 8
Verdict: ACCEPTED
| input |
|---|
| 97 74 |
| correct output |
|---|
| 7178 |
| user output |
|---|
| 7178 |
Test 9
Verdict: ACCEPTED
| input |
|---|
| 58 8 |
| correct output |
|---|
| 464 |
| user output |
|---|
| 464 |
Test 10
Verdict: ACCEPTED
| input |
|---|
| 15 24 |
| correct output |
|---|
| 360 |
| user output |
|---|
| 360 |
Test 11
Verdict: ACCEPTED
| input |
|---|
| 4 7 |
| correct output |
|---|
| 28 |
| user output |
|---|
| 28 |
Test 12
Verdict: ACCEPTED
| input |
|---|
| 906 417 |
| correct output |
|---|
| 377802 |
| user output |
|---|
| 377802 |
Test 13
Verdict: ACCEPTED
| input |
|---|
| 778 105 |
| correct output |
|---|
| 81690 |
| user output |
|---|
| 81690 |
Test 14
Verdict: ACCEPTED
| input |
|---|
| 2 989 |
| correct output |
|---|
| 1978 |
| user output |
|---|
| 1978 |
Test 15
Verdict: ACCEPTED
| input |
|---|
| 2830 5329 |
| correct output |
|---|
| 15081070 |
| user output |
|---|
| 15081070 |
Test 16
Verdict: ACCEPTED
| input |
|---|
| 9 51382 |
| correct output |
|---|
| 462438 |
| user output |
|---|
| 462438 |
Test 17
Verdict: ACCEPTED
| input |
|---|
| 25053 71372 |
| correct output |
|---|
| 1788082716 |
| user output |
|---|
| 1788082716 |
Test 18
Verdict: ACCEPTED
| input |
|---|
| 258180 674616 |
| correct output |
|---|
| 174172358880 |
| user output |
|---|
| 174172358880 |
Test 19
Verdict: ACCEPTED
| input |
|---|
| 8821 2 |
| correct output |
|---|
| 17642 |
| user output |
|---|
| 17642 |
Test 20
Verdict: ACCEPTED
| input |
|---|
| 1742712 9600618 |
| correct output |
|---|
| 16731112196016 |
| user output |
|---|
| 16731112196016 |
Test 21
Verdict: ACCEPTED
| input |
|---|
| 8898606 2936506 |
| correct output |
|---|
| 26130809910636 |
| user output |
|---|
| 26130809910636 |
Test 22
Verdict: ACCEPTED
| input |
|---|
| 82670092 60138633 |
| correct output |
|---|
| 4971666322864236 |
| user output |
|---|
| 4971666322864236 |
Test 23
Verdict: ACCEPTED
| input |
|---|
| 54746871 83822602 |
| correct output |
|---|
| 4589025178578342 |
| user output |
|---|
| 4589025178578342 |
Test 24
Verdict: ACCEPTED
| input |
|---|
| 477252461 1032684 |
| correct output |
|---|
| 492850980435324 |
| user output |
|---|
| 492850980435324 |
Test 25
Verdict: ACCEPTED
| input |
|---|
| 5932935 379 |
| correct output |
|---|
| 2248582365 |
| user output |
|---|
| 2248582365 |
Test 26
Verdict: ACCEPTED
| input |
|---|
| 620114 3126641 |
| correct output |
|---|
| 1938873857074 |
| user output |
|---|
| 1938873857074 |
Test 27
Verdict: ACCEPTED
| input |
|---|
| 452757081 222748761 |
| correct output |
|---|
| 100851078826726641 |
| user output |
|---|
| 100851078826726641 |
Test 28
Verdict: ACCEPTED
| input |
|---|
| 689748332 888826746 |
| correct output |
|---|
| 613066765490487672 |
| user output |
|---|
| 613066765490487672 |
Test 29
Verdict: ACCEPTED
| input |
|---|
| 111337 25 |
| correct output |
|---|
| 2783425 |
| user output |
|---|
| 2783425 |
Test 30
Verdict: ACCEPTED
| input |
|---|
| 809 84435378 |
| correct output |
|---|
| 68308220802 |
| user output |
|---|
| 68308220802 |
Test 31
Verdict: ACCEPTED
| input |
|---|
| 9641697369926504411 425970950212942028697061039529... |
| correct output |
|---|
| 410708299033321711216812810174... |
| user output |
|---|
| 410708299033321711216812810174... |
Test 32
Verdict: ACCEPTED
| input |
|---|
| 793769623129909085108356241071... |
| correct output |
|---|
| 264404012608186879272715560773... |
| user output |
|---|
| 264404012608186879272715560773... |
Test 33
Verdict: ACCEPTED
| input |
|---|
| 8539777831492675800 436 |
| correct output |
|---|
| 3723343134530806648800 |
| user output |
|---|
| 3723343134530806648800 |
Test 34
Verdict: ACCEPTED
| input |
|---|
| 946492187160898604892390431179... |
| correct output |
|---|
| 585982368537725512535970251461... |
| user output |
|---|
| 585982368537725512535970251461... |
Test 35
Verdict: ACCEPTED
| input |
|---|
| 874046401974324184707688863838... |
| correct output |
|---|
| 174556202198322810668657866310... |
| user output |
|---|
| 174556202198322810668657866310... |
Test 36
Verdict: ACCEPTED
| input |
|---|
| 168584663428092347854539803060... |
| correct output |
|---|
| 235958453587245776929148968707... |
| user output |
|---|
| 235958453587245776929148968707... |
Test 37
Verdict: ACCEPTED
| input |
|---|
| 279013912031336395843652482056... |
| correct output |
|---|
| 856375236460411618343887929304... |
| user output |
|---|
| 856375236460411618343887929304... |
Test 38
Verdict: ACCEPTED
| input |
|---|
| 909594443312661242668561455177... |
| correct output |
|---|
| 801297086685128929836268694647... |
| user output |
|---|
| 801297086685128929836268694647... |
Test 39
Verdict: ACCEPTED
| input |
|---|
| 521558480102200460144622364590... |
| correct output |
|---|
| 403176935665359352292583479223... |
| user output |
|---|
| 403176935665359352292583479223... |
Test 40
Verdict: ACCEPTED
| input |
|---|
| 198766521920629467015839613580... |
| correct output |
|---|
| 197951285207558548760833360414... |
| user output |
|---|
| 197951285207558548760833360414... |
Test 41
Verdict: ACCEPTED
| input |
|---|
| 388239940637354291806784217812... |
| correct output |
|---|
| 354893636094929851749498258576... |
| user output |
|---|
| 354893636094929851749498258576... |
Test 42
Verdict: ACCEPTED
| input |
|---|
| 580031950564534684773525167998... |
| correct output |
|---|
| 225288306472433597677862095876... |
| user output |
|---|
| 225288306472433597677862095876... |
Test 43
Verdict: ACCEPTED
| input |
|---|
| 673497493525004204568833306269... |
| correct output |
|---|
| 104167516519697053781119530996... |
| user output |
|---|
| 104167516519697053781119530996... |
Test 44
Verdict: ACCEPTED
| input |
|---|
| 583582406474458495157747860432... |
| correct output |
|---|
| 355985267949419682046226194863... |
| user output |
|---|
| 355985267949419682046226194863... |
Test 45
Verdict: ACCEPTED
| input |
|---|
| 154401310284121033413839709675... |
| correct output |
|---|
| 472687322036571910421947159369... |
| user output |
|---|
| 472687322036571910421947159369... |
Test 46
Verdict: ACCEPTED
| input |
|---|
| 964784520177212016698 135881607827957154173561484162... |
| correct output |
|---|
| 131096471809203739325264543904... |
| user output |
|---|
| 131096471809203739325264543904... |
Test 47
Verdict: ACCEPTED
| input |
|---|
| 506417941420848908877158785176... |
| correct output |
|---|
| 124940484872553056181800567857... |
| user output |
|---|
| 124940484872553056181800567857... |
Test 48
Verdict: ACCEPTED
| input |
|---|
| 278205703909200971326699489015... |
| correct output |
|---|
| 213362541886605761113025837459... |
| user output |
|---|
| 213362541886605761113025837459... |
Test 49
Verdict: ACCEPTED
| input |
|---|
| 488919747667763730629078434642... |
| correct output |
|---|
| 244261035002054726047225565934... |
| user output |
|---|
| 244261035002054726047225565934... |
Test 50
Verdict: ACCEPTED
| input |
|---|
| 683013292533355268532590162229... |
| correct output |
|---|
| 271255985219635665074840248062... |
| user output |
|---|
| 271255985219635665074840248062... |
Test 51
Verdict: ACCEPTED
| input |
|---|
| 701382950383712289025758984281... |
| correct output |
|---|
| 396240397875971182850884660551... |
| user output |
|---|
| 396240397875971182850884660551... |
Test 52
Verdict: ACCEPTED
| input |
|---|
| 950530137216618089651057517232... |
| correct output |
|---|
| 525100658977646195130452101103... |
| user output |
|---|
| 525100658977646195130452101103... |
Test 53
Verdict: ACCEPTED
| input |
|---|
| 758180874616256083097058082046... |
| correct output |
|---|
| 612777382638418549100062437996... |
| user output |
|---|
| 612777382638418549100062437996... |
Test 54
Verdict: ACCEPTED
| input |
|---|
| 282198270649528096385750216226... |
| correct output |
|---|
| 878945962031578099916769892430... |
| user output |
|---|
| 878945962031578099916769892430... |
Test 55
Verdict: ACCEPTED
| input |
|---|
| 374271236006180996628555027124... |
| correct output |
|---|
| 205927043926518428842129271440... |
| user output |
|---|
| 205927043926518428842129271440... |
Test 56
Verdict: ACCEPTED
| input |
|---|
| 789860669365068182777748873091... |
| correct output |
|---|
| 369460448033120451265094062370... |
| user output |
|---|
| 369460448033120451265094062370... |
Test 57
Verdict: ACCEPTED
| input |
|---|
| 826700926013863385104801713448... |
| correct output |
|---|
| 291751287859134397942962144651... |
| user output |
|---|
| 291751287859134397942962144651... |
Test 58
Verdict: ACCEPTED
| input |
|---|
| 947468718382260248801518078140... |
| correct output |
|---|
| 226868697296935607336651841496... |
| user output |
|---|
| 226868697296935607336651841496... |
Test 59
Verdict: ACCEPTED
| input |
|---|
| 177252461103268440789803954968... |
| correct output |
|---|
| 111876380249200192763403085310... |
| user output |
|---|
| 111876380249200192763403085310... |
Test 60
Verdict: ACCEPTED
| input |
|---|
| 393293577943612353036749957226... |
| correct output |
|---|
| 336630505716557163667422969707... |
| user output |
|---|
| 336630505716557163667422969707... |
Test 61
Verdict: ACCEPTED
| input |
|---|
| 320114112664152374910455416563... |
| correct output |
|---|
| 136407754249269979820422504376... |
| user output |
|---|
| 136407754249269979820422504376... |
Test 62
Verdict: ACCEPTED
| input |
|---|
| 152757081122748761316522074282... |
| correct output |
|---|
| 107712372482584798763194835348... |
| user output |
|---|
| 107712372482584798763194835348... |
Test 63
Verdict: ACCEPTED
| input |
|---|
| 889748332988826746683887083103... |
| correct output |
|---|
| 729454517423131565738173030712... |
| user output |
|---|
| 729454517423131565738173030712... |
Test 64
Verdict: ACCEPTED
| input |
|---|
| 311337350148998951898280698942... |
| correct output |
|---|
| 245742878826375358332482490843... |
| user output |
|---|
| 245742878826375358332482490843... |
Test 65
Verdict: ACCEPTED
| input |
|---|
| 709744353788876782171034561202... |
| correct output |
|---|
| 198288295923437797210097622398... |
| user output |
|---|
| 198288295923437797210097622398... |
