QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #762084 | #9597. Grade 2 | ssx | WA | 87ms | 13652kb | C++20 | 1.1kb | 2024-11-19 13:30:26 | 2024-11-19 13:30:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pll pair<ll, ll>
#define ll long long
const int mod = 1e9 + 7;
const int N = 3e6 + 50;
ll res[N];
void solve()
{
ll x, lg, tx, n;
cin >> x >> n;
lg = __lg(x);
if (pow(2, lg) < x) lg ++;
lg = pow(2, lg);
for (int i = 1; i <= lg; i++)
{
tx = ((i * x) ^ x);
if (__gcd(tx, x) == 1) res[i] = res[i - 1] + 1;
else res[i] = res[i - 1];
}
ll l, r, p1, p2, x1, x2, ans;
while (n --)
{
cin >> l >> r;
p1 = l % lg;
p2 = r % lg;
x1 = l / lg;
x2 = r / lg;
if (x1 == x2)
{
ans = res[p2] - res[p1 - 1];
}
else
{
ans = (x2 - x1) * res[lg];
ans -= res[p1];
ans += res[p2];
}
cout << ans << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll T = 1;
//cin >> T;
while (T --)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3900kb
input:
15 2 1 4 11 4514
output:
2 2252
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 52ms
memory: 9116kb
input:
500696 100000 110442401300 646889080214 337192 670162015551 508011001649 508011014425 94418501628 94418501634 824168677375 824168677376 732815842309 795402573302 353241304050 846773277757 622033633276 622033633284 760381702139 760381702143 207714 795408271057 382792 952061527685 686173 331215904334 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #3:
score: 0
Accepted
time: 56ms
memory: 8656kb
input:
465262 100000 119442423888 249533375982 528365238401 528365275157 654839906300 654839906303 135820863700 135820967840 336231 918143221477 568175915485 568176067832 993015103483 993015103488 951474 444595379179 298623434750 298623434751 257961 410491919396 996297715292 996297994388 17765498878 177654...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #4:
score: 0
Accepted
time: 87ms
memory: 13652kb
input:
599394 100000 683408 868635908987 347999512025 347999739145 740945 377178907084 399211757563 399211757568 766968 548821086083 630762 702128377806 756554924031 756554924036 904713771313 904714518208 17026878789 17027129255 11601638470 206412869961 253365321722 253365321730 785476956554 785477402085 2...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #5:
score: -100
Wrong Answer
time: 39ms
memory: 7764kb
input:
255255 100000 693776785134 693776920782 174578728959 174578728960 109045569231 631173362385 470661333171 470661439492 401883 183360880923 436203696728 436203931780 165055 339075075373 640081 299360395352 864237441330 864237509663 730335563579 730335652091 194265481215 194265481219 40664920117 406649...
output:
48406 0 186110004314 37959 65357983201 83815 120861662354 106705381500 24327 31556 1 13697 28081 260202193145 52511483770 4 46174459075 3 175347987986 2 47909 258154440479 327427357800 2 22468 54932 46381156132 45666301682 94552873123 55243 1 152254920557 2 109713294364 91231052949 144890963440 1 19...
result:
wrong answer 2nd lines differ - expected: '1', found: '0'