我公司是做网站开发的怎么纳税,昌图网站推广,怎样免费做外贸网站,怎么做贷款网站5.互质数
题目描述
给定 a, b#xff0c;求 1 ≤ x a^b 中有多少个 x 与 a^b 互质。由于答案可能很大#xff0c;你只需要输出答案对 998244353 取模的结果。
输入格式
输入一行包含两个整数分别表示 a, b#xff0c;用一个空格分隔。
输出格式
输出一行包含一个…5.互质数
题目描述
给定 a, b求 1 ≤ x a^b 中有多少个 x 与 a^b 互质。由于答案可能很大你只需要输出答案对 998244353 取模的结果。
输入格式
输入一行包含两个整数分别表示 a, b用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
2 5样例输出
16题目分析
1.快速幂求解a^b: 要想求解a^b对于b的值越来越大可能会导致运算超时此时我们可以使用快速幂算法通过快速幂算法我们可以很快的求解出a^b的值2.欧拉降指数函数:如果要求 1 ≤ x a^b 中有多少个 x 与 a^b 互质可以采用欧拉函数3.结合上面俩个关键点我们便可解决此题下面一一介绍这两种算法快速幂算法
介绍
快速幂算法Fast Exponentiation Algorithm是一种用于快速计算大数的指数幂的算法。在计算机科学和数学中它是一种高效的方法用于计算形如 x^n 的表达式其中 x 是任意实数n 是一个非负整数。传统的指数运算方法的时间复杂度为 O(n)而快速幂算法的时间复杂度为 O(log n)因此在处理大数时非常高效。实现思路
这个算法的基本思想是利用指数的二进制表示。例如若指数 n 的二进制表示为 1101那么 x^n 就可以分解为 x^(2^0) * x^(2^2) * x^(2^3)其中指数的二进制表示中为 1 的位置对应着 x^n 中需要相乘的部分。这样就可以通过分治的方式快速计算出 x^n。Java代码
举例说明
1024^105
对于整数105的可以分解为64 32 8 1
转换成二进制数可以表现为1101001
1024^1 1024
1024^2 1024^1024
1024^4 1024^2 * 1024^2
1024^8 1024^4 * 1024^4
1024^16 1024^8*1024^8
1024^32 1024^16*1024^16
1024^64 1024^64*1024^64private static long quickPower(long a, long b) {//a为底数 b为指数long result 1;while(b 0) {if (b 1 1) {//如果二进制末位为1result result * a;}a a * a;//表示每一位二进制数要乘的数b b 1;//将二进制数向右移动一位进行缩小 }return result
}欧拉函数
介绍
欧拉函数Eulers Totient Function是一个在数论中非常重要的函数通常用符号φ(n)表示。对于正整数n欧拉函数φ(n)定义为小于等于n且与n互质的正整数的个数。
例如当n8时与8互质的正整数是1, 3, 5, 7因此φ(8) 4。性质
欧拉函数有许多有用的性质其中一些包括
1. 若p为质数则φ(p) p - 1。这是因为质数p的所有小于p的正整数都与p互质。
2. 若m和n互质则φ(mn) φ(m)φ(n)。这是欧拉函数的乘性性质。
3. 对于任意正整数n欧拉函数满足以下的递归关系式若n可以分解为素数因子的乘积则φ(n) n(1 - 1/p1)(1 - 1/p2)...(1 - 1/pk)其中p1, p2, ..., pk是n的不同素因子。Java实现
初始化结果为n。对n进行质因数分解从2开始逐个检查可能的质因数i。如果当前数能够整除n则说明i是n的一个质因数进入循环不断将n除以i直到不能整除为止排除掉n中所有的i因数。更新result减去由i引起的不同的因子个数即result除以i的整数部分。处理剩余的质因数如果n大于1说明n本身就是一个质数更新result减去由n引起的不同的因子个数即result除以n的整数部分。返回最终计算结果。
举例
n 15
n % 2 0 表明2不是n的因数
n % 3 0 表明3是n的因数n/3 5result result - result / 3 表明小于n的质因数不是3的倍数/*由于 4 * 4大于15因而4之后的元素要么重复要么不是15的质因数即i*i n解释对于p * q n 必然存在一个较大的p和一个较小的q(或者二者相等若q*q大于n则p和q一定不是n的质数)*/
剩余较大的因数n 5result result - result / 5为最终结果private static long Euler(long n) {// 计算欧拉函数值long result n; // 初始化结果为n// 对n进行质因数分解for (long i 2; i * i n; i) { // 从2开始逐个检查可能的质因数if (n % i 0) { // 如果当前数能够整除n即i是n的一个质因数while (n % i 0) { // 循环直到n不能再被i整除为止排除掉n中所有的i因数n / i; // 不断将n除以i直到不能整除为止}result result - result / i; // 更新result减去由i引起的不同的因子个数即result除以i的整数部分}}// 处理剩余的质因数if (n 1) { // 如果n本身就是一个质数result result - result / n; // 更新result减去由n引起的不同的因子个数即result除以n的整数部分}return result; // 返回最终计算结果
}Java代码实现
static final long MOD 998244353;public static void main(String[] args) {Scanner sc new Scanner(System.in);long a sc.nextLong();long b sc.nextLong();//欲求小于等于a^b有几个质数与其互质//1.要求小于等于某个数并与其互质个数---欧拉函数//2.要求某个数的幂次---快速幂算法System.out.println(Euler(a) * quickPower(a, b - 1) % MOD);}//欧拉降指数函数用符号φ(n)表示表示小于等于n且与n互质的正整数的个数。private static long Euler(long n) {// 10long result n; // 初始化结果为n// 对n进行质因数分解for (long i 2; i * i n; i) {// 2是质数if (n % i 0) {// 如果n模2为0表明存在公因式为2的因数while (n % i 0) {// 一直与2取余数并除以2使得结果中不再有2的因数n / i;}result result - result / i;}}// 处理剩余的质因数if (n 1) {result result - result / n;}return result;}//快速幂函数private static long quickPower(long a, long b) {long result 1;while (b 0) {//判断末尾位是否在二进制中为1if ((b 1) 1) {result (result * a) % MOD; // 对结果取模避免溢出}a (a * a) % MOD; // 对中间结果取模避免溢出//将二进制数向右移1位使得去掉末尾b b 1;}return result;}System.out.println(Euler(a) * quickPower(a, b - 1) % MOD);的解释
