C - Primitive Root
题意
给定p与m(p为质数)，已知(g ^ (P - 1)) % P == 1且g <= m。求g的个数。
思路
由(g ^ (P - 1)) % P == 1与异或性质a - b <= a ^ b <= a + b，可以推出g = ((k * p + 1) ^ (p - 1))与p * (k - 1) + 2 <= g <= p * (k + 1)。又因为g <= m，则当p * (k + 1) <= m，一定合法；p * (k - 1) + 2 > m一定不合法；二者之间单独判断。
原根(虽然没什么用)：https://zhuanlan.zhihu.com/p/591377528
代码
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mxn = 1e6 + 5;
void solve()
{
int m, p, ans = 0;
scanf("%lld%lld", &p, &m);
// (k < m \ p - 1)一定满足(加上0共n / p个)，(k > (m - 2) / p + 1)一定不满足
int minn = m / p, maxn = (m - 2) / p + 1;
if ((m - 2) % p) // 考虑取整
{
maxn++;
}
for (int k = minn; k <= maxn; k++) // 二者之间单独判断，数据量很小
{
int g = ((k * p + 1) ^ (p - 1));
if (g <= m)
{
ans++;
}
}
printf("%lld\n", m / p + ans);
}
signed main()
{
int T = 1;
scanf("%lld", &T);
while (T--)
{
solve();
}
return 0;
}
F - Equivalent Rewriting
题意
思路
代码
G - Knapsack
题意
思路
代码
I - Counter
题意
n次操作，操作分两种：归零或+1；m个条件，每个条件给定a与b，表示第a次操作后值为b。问是否存在所给情况。
思路
按a给操作排序，由于每次只能+1，故b <= a；对于相邻两次操作，相差a_i - a_j次操作，可以全部加(b_j - b_i == a_j - a_i)，也可以几次归零几次加，就可以得出范围：b_j >= 0(全归零)且b_j <= s2 - a1 - 1(归零一次)，但题目保证了b >= 0，故只用看后者。
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
void solve()
{
int n, m;
scanf("%lld%lld", &n, &m);
vector<pii> v(m);
for (int i = 0; i < m; i++)
{
scanf("%lld%lld", &v[i].first, &v[i].second);
}
if (m == 1) // 特判
{
printf(v[0].second > v[0].first ? "No\n" : "Yes\n");
return;
}
sort(v.begin(), v.end());
for (int i = 0; i < m - 1; i++)
{
int a1 = v[i].first, b1 = v[i].second;
int a2 = v[i + 1].first, b2 = v[i + 1].second;
if (b1 > a1 || b2 > a2)
{
printf("No\n");
return;
}
if (b2 - b1 == a2 - a1 || b2 <= a2 - a1 - 1) // 全加或归零一次后全加
{
continue;
}
else
{
printf("No\n");
return;
}
}
printf("Yes\n");
}
signed main()
{
int T = 1;
scanf("%lld", &T);
while (T--)
{
solve();
}
return 0;
}