61 lines
993 B
C++
61 lines
993 B
C++
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
#define int long long
|
|
|
|
int l,r,m;
|
|
|
|
int lgpow(int x,int y)
|
|
{
|
|
int z = 1;
|
|
while (y != 0)
|
|
{
|
|
if (y % 2 == 1)
|
|
z = z * x % m;
|
|
x = x * x % m;
|
|
y /= 2;
|
|
}
|
|
return z;
|
|
}
|
|
|
|
int sump2(int x)
|
|
{
|
|
return lgpow(2,x + 1) - 1;
|
|
}
|
|
|
|
void testcase()
|
|
{
|
|
cin >> l >> r >> m;
|
|
int ans = 0;
|
|
if (r - l + 1 <= 3)
|
|
{
|
|
for (int i = l; i <= r; i++)
|
|
ans += lgpow(2,(i - 1) / 2);
|
|
cout << ans % m << '\n';
|
|
}
|
|
else
|
|
{
|
|
if (l % 2 == 0)
|
|
ans += lgpow(2,(l - 1) / 2),l++;
|
|
if (r % 2 == 1)
|
|
ans += lgpow(2,(r - 1) / 2),r--;
|
|
int st = (l + 1) / 2,fin = (r / 2);
|
|
ans += sump2(fin) - sump2(st - 1);
|
|
ans += m;
|
|
cout << ans % m << '\n';
|
|
}
|
|
}
|
|
|
|
signed main()
|
|
{
|
|
ios_base::sync_with_stdio(false);
|
|
cin.tie(NULL);
|
|
cout.tie(NULL);
|
|
int tc;
|
|
cin >> tc;
|
|
while (tc--)
|
|
testcase();
|
|
return 0;
|
|
}
|