A. 整数幂
给定两个整数 k k k 和 l l l，请判断是否存在一个正整数 n n n，满足 k n = l kn=l kn=l。
输入格式
第一行包含整数 T T T，表示共有 T T T 组测试数据。
每组数据占两行，第一行包含整数 k k k，第二行包含整数 l l l。
输出格式
每组数据输出一行结果，如果存在
n
n
n，则输出 YES，否则输出 NO。
数据范围
前三个测试点满足，
2
≤
k
,
l
≤
100
2\leq k,l\leq 100
2≤k,l≤100。
所有测试点满足，
1
≤
T
≤
10
1\leq T\leq 10
1≤T≤10，
2
≤
k
,
l
≤
2
31
−
1
2\leq k,l\leq 2^{31}−1
2≤k,l≤231−1。
输入样例：
2
5
25
3
8
输出样例：
YES
NO
题目分析：
手速题，暴力枚举。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL get_c(int a, int k)
{
LL res = 1;
for (int i = 0; i < k; i ++ )
res *= a;
return res;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
int k, l;
cin >> k >> l;
bool flag = false;
for (int i = 0; i <= 50; i ++ )
if (get_c(k, i) == l)
{
flag = true;
break;
}
if (flag) puts("YES");
else puts("NO");
}
return 0;
}
B. 变成1
给定一个二进制数 x x x，在它变为 1 1 1 之前，不断对它进行如下操作：
-
如果 x x x 为奇数，则将 x x x 加 1 1 1。
-
如果 x x x 为偶数，则将 x 除以 2 2 2。
请问，多少次操作后， x x x 会变为 1 1 1。
输入格式
共一行，一个 01 字符串，表示二进制数 x x x。
输出格式
一个整数，表示所需操作次数。
数据范围
前六个测试点满足，
x
x
x 的位数不超过
11
11
11。
所有测试点满足，
x
x
x 的首位不为
0
0
0，且位数不超过
1
0
6
10^6
106。
输入样例1：
1
输出样例1：
0
输入样例2：
1001001
输出样例2：
12
输入样例3：
101110
输出样例3：
8
题目分析：
由于 x x x 最多可以是 1 0 6 10^6 106 位，因此需要使用高精度根据题意进行模拟。
但实际上可以不用高精度的方式，转而对二进制数串进行操作，利用双指针的思想处理。
例如对于一个给定的二进制数串 101110，从后往前操作：
手动模拟一下可以发现规律：若当前这一位是
0
0
0 时，直接操作数 + 1，然后右移一位；若当前这一位是
1
1
1，需要加
1
1
1，那就需要找到所有连续的
1
1
1 的个数，因为加上
1
1
1 之后这些连续的
1
1
1 都会由于进位的原因全部变成
0
0
0，那么操作数就等于连续
1
1
1 的个数加上
1
1
1。
这样，我们就可以设置两个指针 i i i 和 j j j，然后累加操作步数即可，具体步骤见代码。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
reverse(str.begin(), str.end()); // 将 01 串倒过来操作
int cnt = 0;
for (int i = 0; i < str.size() - 1; i ++ )
{
if (str[i] == '0') ++ cnt;
else
{
int j = i;
while (j < str.size() && str[j] == '1') j ++ ;
cnt += j - i + 1;
str[j] = '1';
i = j - 1;
}
}
cout << cnt << endl;
return 0;
}
C. 最大公约数
给定两个正整数 a , m a,m a,m，其中 a < m a<m a<m。
请你计算，有多少个小于 m m m 的非负整数 x x x 满足：
gcd ( a , m ) = gcd ( a + x , m ) \gcd(a,m) = \gcd(a+x,m) gcd(a,m)=gcd(a+x,m)
输入格式
第一行包含整数 T T T，表示共有 T T T 组测试数据。
每组数据占一行，包含两个整数 a , m a,m a,m。
输出格式
每组数据输出一行结果，一个整数，表示满足条件的非负整数 x x x 的个数。
数据范围
前三个测试点满足，
1
≤
T
≤
10
1\leq T\leq 10
1≤T≤10。
所有测试点满足，
1
≤
T
≤
50
1\leq T\leq 50
1≤T≤50，
1
≤
a
<
m
≤
1
0
10
1\leq a<m\leq 10^{10}
1≤a<m≤1010。
输入样例：
3
4 9
5 10
42 9999999967
输出样例：
6
1
9999999966
题目分析：
a < m a < m a<m。令 d = gcd ( a , m ) = gcd ( a + x , m ) d = \gcd(a, m) = \gcd(a + x, m) d=gcd(a,m)=gcd(a+x,m)，则 d ∣ a , d ∣ m d\mid a,\ d\mid m d∣a, d∣m，而又 ∵ \because ∵ d ∣ a , d ∣ m d\mid a,\ d\mid m d∣a, d∣m，且 d ∣ ( a + x ) d\mid (a + x) d∣(a+x)， ∴ d ∣ x \therefore d\mid x ∴d∣x。
令 a ′ = a d , m ′ = m d , x ′ = x d a' = \dfrac{a}{d},\ m' = \dfrac{m}{d},\ x' = \dfrac{x}{d} a′=da, m′=dm, x′=dx，则 gcd ( a ′ + x ′ , m ′ ) = 1 \gcd(a' + x', m') = 1 gcd(a′+x′,m′)=1，问题转化为：有多少个满足要求的 x ′ x' x′ 使得 ( a ′ + x ′ ) (a' + x') (a′+x′) 与 m ′ m' m′ 互质。
∵ 0 ≤ x < m \because 0\leq x < m ∵0≤x<m， ∴ 0 ≤ x ′ < m \therefore 0\leq x' < m ∴0≤x′<m，两边同加上 a ′ a' a′，得 a ′ ≤ x ′ < a ′ + m ′ a'\leq x' < a' + m' a′≤x′<a′+m′，即求 [ a ′ , a ′ + m ′ ) [a',\ a' + m') [a′, a′+m′) *有多少个数与 m ′ m' m′ 互质。
图中红色的两段 [ 0 , a ′ ) [0, a') [0,a′) 和 [ m ′ , a ′ + m ′ ) [m', a' + m') [m′,a′+m′) 在 m o d m ′ \bmod\ m' mod m′ 的意义下数值是一样的，那么与之互质的数的情况也就是一样的，故我们求 [ a ′ , a ′ + m ′ ) [a', a' + m') [a′,a′+m′) 中有多少个与 m ′ m' m′ 互质的数，就可以转化为求 [ 0 , m ′ ) [0, m') [0,m′) 中与 m ′ m' m′ 互质的数的个数，求一下 m ′ m' m′ 的欧拉函数 φ ( m ′ ) \varphi (m') φ(m′) 即可。
关于欧拉函数的求解和证明过程，可以参考：AcWing 873. 欧拉函数。
注意，本题不可使用 筛法求欧拉函数 进行求解，筛法求欧拉函数时间复杂度是线性的，可以求出 1 ∼ n 1\sim n 1∼n 中每个数的欧拉函数，但本题的部分数据可能达到 1 0 10 10^{10} 1010，线性筛不能够在时限内求出所需要数的欧拉函数。
时间复杂度分析：
每组数据只需要求出其欧拉函数即可，复杂度为 n \sqrt n n ，一共有 50 50 50 组数据，值最大可达 1 0 10 10^{10} 1010，因此总的计算量约为 50 × 1 0 10 ≈ 5 × 1 0 6 50\times \sqrt {10^{10}} \approx 5\times 10^6 50×1010 ≈5×106。
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
LL phi(LL m)
{
LL res = m;
for (int i = 2; i <= m / i; i ++ )
if (m % i == 0)
{
res = res / i * (i - 1);
while (m % i == 0) m /= i;
}
if (m > 1) res = res / m * (m - 1);
return res;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
LL a, m;
cin >> a >> m;
m = m / gcd(a, m);
cout << phi(m) << endl;
}
return 0;
}