当前位置：首页 > news >正文

模运算和快速幂

news 2025/8/22 15:06:19

文章目录

- 模运算
- 快速幂

模运算

模运算是大数运算中的常用操作。如果一个数太大，无法直接输出，或者不需要直接输出，则可以对它取模，缩小数值再输出。取模可以防止溢出，这是常见的操作。

取模运算一般要求a和m的符号一致，即都为正数或都为负数。如果正负不同，那么请小心处理模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p

(a - b) % p = (a % p - b % p) % p

注意负数取模的问题，尽量保证（a-b)为正数，如果a-b为负数则可以写成
（（a-b)%p+p）%p 例如 -3%5=-3 （-3%5+5）%5=2

(a * b) % p = (a % p * b % p) % p

(a^b) % p = ((a % p)^b) % p
模运算例题

public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);long a=scan.nextLong();long b=scan.nextLong();long c=scan.nextLong();long day=0;long x=a*5+b*2;long week=c/x;long last=c%x;if(last>0) {if(last<5*a){long m=last/a;if(last%a>0)day=m+1;elseday=m;}else{last-=5*a;long m=last/b;if(last%b>0)day=5+m+1;elseday=5+m;}}System.out.println(week*7+day);scan.close();}
}

例题代码。

快速幂

1.算法思想
将指数n表示为其二进制形式，例如，n = 13 可表示为 1101。
从二进制形式的最低位开始，逐位检查：如果当前位为1，则将结果乘以对应的底数的幂每次将底数的幂平方，即底数的幂乘以自身，同时将指数右移一位。
继续处理下一位，直到所有位都处理完毕，此时得到最终结果。
1、当指数是偶数时，我们可以让指数除以2，底数乘以底数 2、当指数是奇数时，我们可以将指数减1变为偶数

当幂%2==0，也就是当幂为偶数时，根据幂的运算法则，我们可以将幂除以2，然后底数进行平方操作，值保持不变。

当幂%2= =1,也就是当幂为奇数时，将幂为奇数的底数保存起来，再对幂-1，重复上面的操作。

最后的结果就是将幂为奇数的底数综合相乘。

long long int quik_power(int base, int power)
{long long int result = 1;while (power > 0)           //指数大于0进行指数折半，底数变其平方的操作{if (power % 2 == 1)     //指数为奇数{power -= 1;         //指数减一power /= 2;         //指数折半result *= base;     //分离出当前项并累乘后保存base *= base;       //底数变其平方}else                    //指数为偶数{power /= 2;         //指数折半base *= base;       //底数变其平方}}return result;              //返回最终结果
}
效率更高的写法
```java
long long int quik_power(int base, int power)
{long long int result = 1;while (power > 0)           //指数大于0进行指数折半，底数变其平方的操作{if (power & 1)			//指数为奇数，power & 1这相当于power % 2 == 1result *= base;     //分离出当前项并累乘后保存power >>= 1;			//指数折半,power >>= 1这相当于power /= 2;base *= base;           //底数变其平方}return result;              //返回最终结果
}

`
在这里插入图片描述

public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);long b=scan.nextLong();long p=scan.nextLong();long k=scan.nextLong();long s=1;while(p>0){if((p&1)==1){s=s*b%k;}b=b*b%k;p>>=1;}System.out.println(s);scan.close();}
}

快速幂

public class Main {static long ksm(long a,long b,long n){long ret=1;while(b>0){if((b&1)==1){ret=ret*a%n;}a=a*a%n;b>>=1;}return ret;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);long a=scan.nextLong();long b=scan.nextLong();long n=scan.nextLong();long x=ksm(10,n+2,b*1000);System.out.println(a*x%(b*1000)/b);scan.close();}
}