QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#695172 | #7735. Primitive Root | cxzcxccd | TL | 0ms | 0kb | C++20 | 1.4kb | 2024-10-31 19:27:33 | 2024-10-31 19:27:36 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
typedef pair<int, int> PII;
int a[N];
void solve()
{
int p, m;
cin >> p >> m;
int loop = -1;
// 确定循环节
for (int i = 0; i <= 100; i++)
{
if (a[i] >= p)
{
loop = i;
break;
}
}
// vector<int> u;
// for (int i = 1; i <= a[loop] + 1; i++)
// {
// int w = (i - 1ll) * p + 1ll;
// int g = w ^ (p - 1ll);
// u.push_back(g);
// }
// sort(u.begin(), u.end());
int first = 0;
// 找第一个数
for (int i = 0; i <= 100; i++)
{
int x = i ^ (p - 1ll);
if (x % p == 1ll)
{
first = i;
break;
}
}
if (m < first)
{
cout << 0 << '\n';
return;
}
int dx = p * a[loop];
int ans = (m - first) / dx;
int v = first + ans * dx;
ans = ans * loop + 1ll;
for (int i = v + 1; i <= m; i++)
{
if (((i ^ (p - 1ll)) % p) == 1ll)
ans++;
}
cout << ans << '\n';
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
a[0] = 1;
for (int i = 1; i <= 2e5; i++)
a[i] = a[i - 1] * 2ll;
int t;
cin >> t;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 2 0 7 11 1145141 998244353