第二十一周
1. 整数幂
第一种思路
判断是否存在一个整数 $n$, 令 $k^n = l$, 可以转化成判断 $l$ 的因子是否全是 $k$。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int T;
int k, l;
int a[N];
int main()
{
scanf("%d", &T);
while (T -- )
{
bool flag = true;
scanf("%d %d", &k, &l);
while (l > 1)
{
if (l % k)
{
flag = false;
break;
}
l /= k;
}
if (!flag) puts("NO");
else puts("YES");
}
return 0;
}
2. 变成1
第一种思路
我们可以将两个操作进行如下转换。
如果二进制数为偶数,除二等于去掉二进制数最末尾的 $0$。
如果二进制数为奇数,加一等于将从后往前的第一个 $0$ 置为 $1$, 此 $0$ 后面的 $1$ 都置为 $0$。
#include <bits/stdc++.h>
using namespace std;
string s;
int cnt;
int main()
{
cin >> s;
while (s.size() > 1)
{
int se = s.size();
if (s[se - 1] == '0') s = s.erase(se - 1, 1);
else
{
for (int i = se; i >= 1; i -- )
{
if (s[i - 1] == '0')
{
s[i - 1] = '1';
break;
}
else s[i - 1] = '0';
}
}
cnt ++;
}
if (s[0] == '0') cnt ++;
cout << cnt;
return 0;
}
3. 最大公约数
第一种思路
因为设 $gcd(a, m) = Gcd$, 可知, 当 $gcd(a + x, m) = gcd(a, m) = Gcd$ 时,
由于 $a, m$ 分别除以 $Gcd$ 后一定是互质的,不然有更大的公因数。
所以,我们可以得到 $gcd(\frac{a + x}{Gcd},\frac{m}{Gcd}) = 1$,
即 $\frac{a + x}{Gcd}$ 和 $\frac{m}{Gcd}$ 互质,
由于其中 $a < m$, 所以我们可以将其分为两种情况。
首先,就是当 $a + x < m$ 时,$\frac{a + x ∈ [0 ~ m - a)}{Gcd}$ 和 $\frac{m}{Gcd}$ 互质。
也就是求 $[\frac{a}{Gcd}, \frac{m}{Gcd})$ 和 $\frac{m}{Gcd}$ 中互质的数的个数。
由于 $gcd(x, y) = gcd(x - y, y)$
当 $a + x >= m$ 时,求的是 $[0, \frac{a}{Gcd})$ 和 $\frac{m}{Gcd}$ 中互质的数的个数。
取两种情况的并集可得,本题所求是 $[0, \frac{m}{Gcd})$ 和 $\frac{m}{Gcd}$ 互质的数的个数。
根据算法基础课所学,可以转换成求 $\frac{m}{Gcd}$ 的欧拉函数
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL T;
LL _gcd(LL a, LL b)
{
if (b == 0) return a;
return _gcd(b, a % b);
}
LL phi(LL n)
{
LL res = n;
for (int i = 2; i <= n / i; i ++ )
{
if (n % i == 0) res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) res = res / n * (n - 1);
return res;
}
int main()
{
scanf("%lld", &T);
while (T -- )
{
LL a, m;
scanf("%lld %lld", &a, &m);
LL gcd = _gcd(a, m);
LL ans = phi(m / gcd);
printf("%lld\n", ans);
}
return 0;
}
个人感触
这次周赛是我第一次成功 AK的周赛,突然想起于3个月前初学时,一道题都不会做的境况。
我的获益确实不少,这一切的功劳,我想大半是拜 $y$ 总所赐,我从一名初学者变成了如今的 提高组选手,当然,还是垫底的。
但是,我已经足够满足了qwq, 最后祝福各位和我年龄相仿的中小学生,或者是大一点哥哥姐姐在之后的编程路上披荆斩棘。
推荐一个我的 分享
第三题代码 _gcd改成__gcd有惊喜
qwq,主要是 CCF不让用