整数幂
变成1
模拟——因为每个情况的方案都是唯一的。
- 首先明确二进制如何判断奇偶性,最后一位的奇偶性为标准。
- 如果 二进制 为奇数,则将 二进制 加1,可能会进位。
- 如果 二进制 为偶数,则将 二进制 除以二,相当于二进制少一位数。
- 如果想变成1,需要使二进制减位。也就是二进制为偶数,但二进制可能为奇数,所以需要进行两次操作,即将其变成偶数再变成奇数。
# python自带的默认数的范围是无限大
x = input()
n = len(x)
res = 0
if (x == '1' and n == 1):
res = 0
else:
acc = 0
# 在(0, n - 1]范围内,因为x首位不为0.
for i in range(n - 1, 0, -1):
tmp_sum = int(x[i]) + acc
acc = tmp_sum // 2 #进位
cur = tmp_sum % 2 #余数用来判断奇偶性
if (cur == 0):
res += 1
else :
res += 2
acc += 1
if (acc):
res += 1
print(res)
最大公约数
已知条件
- $a < m$
- $gcd(a, m) = gcd(a + x, m)$
其中$d = gcd(a, m) = gcd(a + x, m)$。
则有$\because d | a、d | m 且 d | (a + x)$。
$\therefore d | x$(根据$d|a,d|b推出d|(ma + nb)$)
则有$a^{‘} = \frac{a}{d},m^{‘} = \frac{m}{d},x^{‘} = \frac{x}{d}$。
$gcd(a^{‘}+x^{‘},m^{‘}) = 1$ (最大公约数为1说明互质)
$\because 0\leq x < m$
$\therefore 0\leq x^{‘} < m^{‘}$
$\therefore 问题转化为a^{‘} \sim a^{‘} + m^{‘} - 1$中总共有多少个数与$m^{‘}互质$。
也就是欧拉函数。
C++代码:
#include <iostream>
#include <cstdio>
#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 x)
{
LL res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);//不能直接套公式计算,化简一下,避免溢出。
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 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;
}
python代码:
t = int(input())
def gcd(a, b):
return (a if (b == 0) else gcd(b, a % b)) # √
#return a if (b == 0) else return gcd(b, a % b) ×
def divide(a):
res = a
i = 2
while (i * i <= a):
if (a % i == 0):
res = res // i * (i - 1)
while (a % i == 0):
a = a // i
i += 1
if (a > 1):
res = res // a * (a - 1)
return res
while (t):
a, m = map(int, input().split())
print(divide(m // gcd(a, m)))
t -= 1
#注意两点: ①整除'//' ②循环while的局部变量需要改变。比如: t -= 1、i += 1。