报数【2024五一模拟赛】
2025年1月5日大约 1 分钟
#include <bits/stdc++.h>
using namespace std;
int T;
int n, x;
set<int> ans;
bool check(int n, int k, int x)
{
int pos = n % (2 * k - 2);
if (pos == 0)
pos = 2 * k - 2;
if (pos <= k)
return pos == x;
return k - (pos - k) == x;
}
int cal()
{
ans.clear();
// (n - x) % (2k - 2) == 0
for (int i = 1; i * i <= n - x; i++)
{
// i == 2k - 2
if ((n - x) % i == 0)
{
// 因子 i
if ((i + 2) % 2 == 0)
{
int k = (i + 2) / 2;
if (ans.find(k) == ans.end())
{
if (check(n, k, x))
ans.insert(k);
}
}
// 因子 (n - x) / i
if (((n - x) / i + 2) % 2 == 0)
{
int k = ((n - x) / i + 2) / 2;
if (ans.find(k) == ans.end())
{
if (check(n, k, x))
ans.insert(k);
}
}
}
}
// (n + x - 2) % (2k - 2) == 0
for (int i = 1; i * i <= n + x - 2; i++)
{
// i == 2k - 2
if ((n + x - 2) % i == 0)
{
// 因子 i
if ((i + 2) % 2 == 0)
{
int k = (i + 2) / 2;
if (ans.find(k) == ans.end())
{
if (check(n, k, x))
ans.insert(k);
}
}
// 因子 (n + x - 2) / i
if (((n + x - 2) / i + 2) % 2 == 0)
{
int k = ((n + x - 2) / i + 2) / 2;
if (ans.find(k) == ans.end())
{
if (check(n, k, x))
ans.insert(k);
}
}
}
}
return ans.size();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--)
{
cin >> n >> x;
cout << cal() << "\n";
}
return 0;
}
/*
2k-2 为周期
必要条件为:
如果处于上升:n % (2k - 2) == x
如果处于下降:k - (n % (2k - 2) - k) == x
即
1. (n - x) % (2k - 2) == 0
2. (2k - 2) - (n % (2k - 2)) == x - 2
n % (2k - 2) + (x - 2) == (2k - 2)
(n + x - 2) % (2k - 2) == 0
当然这个条件看上去就不充分,再 $O(1)$ 验证一下就好了
*/