QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#495035 | #9158. 分数 | ningago | 100 ✓ | 4317ms | 6000kb | C++14 | 3.8kb | 2024-07-27 18:13:23 | 2024-07-27 18:13:23 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <cctype>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
namespace uvu
{
#define LOCAL ________________DONT_DEFINE_ME_______________
#define ll long long
#define inf 0x3f3f3f3f
// #define int long long
// #define inf 0x3f3f3f3f3f3f3f3fll
#define infll 0x3f3f3f3f3f3f3f3fll
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define gline debug("now is #%d\n", __LINE__)
#define pii std::pair <int, int>
#define mkp std::make_pair
#define fi first
#define se second
char _ST_;
const int BUFSIZE = (1 << 20);
char ibuf[BUFSIZE], *iS = ibuf, *iT = ibuf;
char obuf[BUFSIZE], *oS = obuf, *oT = obuf + BUFSIZE;
char getc()
{
#ifdef LOCAL
return getchar();
#else
if(iS == iT) iT = (iS = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
return (iS == iT) ? EOF : *iS++;
#endif
#define getchar ERR
}
void Flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; }
struct Flusher { ~Flusher() { Flush(); } }iamflusher;
void putc(char c)
{
#ifdef LOCAL
putchar(c);
#else
*oS++ = c;
if(oS == oT) Flush();
#endif
}
template <typename T = int> T read()
{
T x = 0, f = 1; char c = getc();
for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
for(; isdigit(c); c = getc()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
template <typename T> void print(T x, char c)
{
static int sta[BUFSIZE], top;
top = 0;
if(x < 0) putc('-'), x *= -1;
if(!x) sta[++top] = 0;
for(; x; x /= 10) sta[++top] = x % 10;
for(; top; putc(sta[top--] ^ 48));
if(c) putc(c);
}
int readstr(char *s, int base)
{
int idx = base - 1; char c = getc();
for(; !(isdigit(c) || isalpha(c) || c == '#' || c == '.'); c = getc());
for(; isdigit(c) || isalpha(c) || c == '#' || c == '.' ; c = getc()) s[++idx] = c;
return idx - base + 1;
}
void printf(const char *s) { for(; *s; s++) putc(*s); }
template <typename T, typename ... Args >
void printf(const char *s, T x, Args ... flgt)
{
for(; *s; s++)
{
if(*s != '%') { putc(*s); continue; }
s++; if(*s == 'd') print(x, 0);
else if(*s == 'c') putc(x);
printf(s + 1, flgt ...);
return;
}
}
template <typename T> void ckmin(T &x, T y) { x = x < y ? x : y; }
template <typename T> void ckmax(T &x, T y) { x = x > y ? x : y; }
#define mod 998244353
// #define mod 1000000007
int sm(int x) { return x >= mod ? x - mod : x; }
void plus_(int &x, int y) { x = sm(x + y); }
void mul_(int &x, int y) { x = 1ll * x * y % mod; }
int ksm(int a, int b) { int flg = 1; for(; b; b >>= 1, mul_(a, a)) if(b & 1) mul_(flg, a); return flg; }
int n, m; ll ans = 0;
bool calc(int a, int b, int c, int d, int l)
{
int amn = a * l + b, bmn = c * l + d;
if(amn > m) return 0;
if(bmn > m) return 0;
if(amn > n && bmn > n) return 0;
int flg = 1, res = 0; //printf("[%d %d %d %d %d]\n", a, b, c, d, l);
if(!a && !c)
{
flg &= (res = calc(c, d, a + 2 * d, b, l));
for(int i = 1; flg; i++) flg &= calc(c, d, a, b + 2 * d * i, std::max(l, i + 1));
}
else
{
res = 1;
if(amn <= n) ans += std::min(a ? (n - amn) / a + 1 : inf, (m - bmn) / c + 1);
if(bmn <= n) ans += std::min((n - bmn) / c + 1, a ? (m - amn) / a + 1 : inf);
for(int i = 1; flg; i++) flg &= calc(c, d, a + 2 * c * i, b + 2 * d * i, std::max(l, i));
}
return res;
}
void solve()
{
// memset(h, idx = -1, sizeof(h));
n = read(), m = read(); if(n > m) n ^= m ^= n ^= m;
calc(0, 0, 0, 1, 1); print(ans, '\n');
}
void init()
{
}
char _ED_;
void mian()
{
debug("%.3f MB\n", abs(&_ST_ - &_ED_) / 1024.0 / 1024);
init();
int T = 1;
for(; T; solve(), T--);
}
#ifdef int
#undef int
#endif
}
int main()
{
// freopen("tmp.in", "r", stdin);
// freopen("tmp.out", "w", stdout);
uvu::mian(); return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 5828kb
input:
99 99
output:
406
result:
ok 1 number(s): "406"
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 5936kb
input:
98 97
output:
405
result:
ok 1 number(s): "405"
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 5932kb
input:
99 96
output:
396
result:
ok 1 number(s): "396"
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 5856kb
input:
995 977
output:
11153
result:
ok 1 number(s): "11153"
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 5936kb
input:
991 990
output:
11220
result:
ok 1 number(s): "11220"
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 5932kb
input:
976 968
output:
10900
result:
ok 1 number(s): "10900"
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 5972kb
input:
7602 7864
output:
215706
result:
ok 1 number(s): "215706"
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 5864kb
input:
7959 7735
output:
220256
result:
ok 1 number(s): "220256"
Pretest #9:
score: 5
Accepted
time: 1ms
memory: 5912kb
input:
7878 7863
output:
221162
result:
ok 1 number(s): "221162"
Pretest #10:
score: 5
Accepted
time: 1ms
memory: 5932kb
input:
7788 7658
output:
215323
result:
ok 1 number(s): "215323"
Pretest #11:
score: 5
Accepted
time: 3ms
memory: 5996kb
input:
95399 99767
output:
8285295
result:
ok 1 number(s): "8285295"
Pretest #12:
score: 5
Accepted
time: 3ms
memory: 5912kb
input:
98051 99642
output:
8439713
result:
ok 1 number(s): "8439713"
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 5912kb
input:
95624 96007
output:
8068127
result:
ok 1 number(s): "8068127"
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 5876kb
input:
99208 98047
output:
8412610
result:
ok 1 number(s): "8412610"
Pretest #15:
score: 5
Accepted
time: 49ms
memory: 5872kb
input:
997417 967722
output:
229917323
result:
ok 1 number(s): "229917323"
Pretest #16:
score: 5
Accepted
time: 48ms
memory: 5912kb
input:
987807 956529
output:
226426912
result:
ok 1 number(s): "226426912"
Pretest #17:
score: 5
Accepted
time: 47ms
memory: 5932kb
input:
971654 984345
output:
228363805
result:
ok 1 number(s): "228363805"
Pretest #18:
score: 5
Accepted
time: 750ms
memory: 5936kb
input:
7892259 7983727
output:
4647501224
result:
ok 1 number(s): "4647501224"
Pretest #19:
score: 5
Accepted
time: 3260ms
memory: 5860kb
input:
7937869 29796968
output:
15197555613
result:
ok 1 number(s): "15197555613"
Pretest #20:
score: 5
Accepted
time: 4317ms
memory: 5860kb
input:
29717543 29510173
output:
30904211576
result:
ok 1 number(s): "30904211576"
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 5916kb
input:
96 98
output:
396
result:
ok 1 number(s): "396"
Test #2:
score: 5
Accepted
time: 1ms
memory: 5852kb
input:
100 99
output:
408
result:
ok 1 number(s): "408"
Test #3:
score: 5
Accepted
time: 0ms
memory: 5796kb
input:
99 99
output:
406
result:
ok 1 number(s): "406"
Test #4:
score: 5
Accepted
time: 1ms
memory: 5972kb
input:
963 951
output:
10634
result:
ok 1 number(s): "10634"
Test #5:
score: 5
Accepted
time: 1ms
memory: 5912kb
input:
958 974
output:
10795
result:
ok 1 number(s): "10795"
Test #6:
score: 5
Accepted
time: 1ms
memory: 5936kb
input:
966 990
output:
11003
result:
ok 1 number(s): "11003"
Test #7:
score: 5
Accepted
time: 1ms
memory: 5972kb
input:
7958 7947
output:
224482
result:
ok 1 number(s): "224482"
Test #8:
score: 5
Accepted
time: 1ms
memory: 5936kb
input:
7623 7730
output:
213444
result:
ok 1 number(s): "213444"
Test #9:
score: 5
Accepted
time: 1ms
memory: 5972kb
input:
7845 7783
output:
218916
result:
ok 1 number(s): "218916"
Test #10:
score: 5
Accepted
time: 1ms
memory: 5996kb
input:
7881 7773
output:
219451
result:
ok 1 number(s): "219451"
Test #11:
score: 5
Accepted
time: 3ms
memory: 5852kb
input:
99414 98698
output:
8465217
result:
ok 1 number(s): "8465217"
Test #12:
score: 5
Accepted
time: 0ms
memory: 5860kb
input:
98249 96148
output:
8237486
result:
ok 1 number(s): "8237486"
Test #13:
score: 5
Accepted
time: 3ms
memory: 5936kb
input:
99003 96832
output:
8324931
result:
ok 1 number(s): "8324931"
Test #14:
score: 5
Accepted
time: 3ms
memory: 5996kb
input:
98266 96030
output:
8231065
result:
ok 1 number(s): "8231065"
Test #15:
score: 5
Accepted
time: 46ms
memory: 6000kb
input:
968207 958885
output:
223522215
result:
ok 1 number(s): "223522215"
Test #16:
score: 5
Accepted
time: 49ms
memory: 5976kb
input:
959846 998397
output:
228770873
result:
ok 1 number(s): "228770873"
Test #17:
score: 5
Accepted
time: 47ms
memory: 5916kb
input:
965821 972280
output:
225359210
result:
ok 1 number(s): "225359210"
Test #18:
score: 5
Accepted
time: 742ms
memory: 5860kb
input:
7855098 7962479
output:
4622947400
result:
ok 1 number(s): "4622947400"
Test #19:
score: 5
Accepted
time: 3230ms
memory: 5932kb
input:
7841076 29648718
output:
15040798710
result:
ok 1 number(s): "15040798710"
Test #20:
score: 5
Accepted
time: 4266ms
memory: 5940kb
input:
29365129 29012208
output:
30267839959
result:
ok 1 number(s): "30267839959"
Extra Test:
score: 0
Extra Test Passed