大数取余运算(详解)

缺乏、安全感 2023-10-04 15:45 29阅读 0赞

### 大数取余运算(详解) ###

//(19^3 mod 23)^2 mod 31=25
    //a=19 b=3 c=23 d=2 e=31
    #include<stdio.h>
    long long powMod(int a,int b,int c)
    {
        
        int result = 1;
        while(b)
        {
        
            if(b % 2 == 1)   //3%2=1    1%2=1
            result = result * a % c;  
    		  //1*19%23=19   19*16%23=5
    		  
    		 
            b/= 2;          //b=b/2  b=3/2=1(int)  b=1/2=0(int) 退出循环 
            a = a * a % c;  //a=a*a%c=16 
        }
        return result;  //返回值5 
    }
    
    int main()
    {
        
    	int a,b,c,d,e;
    	int i=1;
    	printf("输入a,b,c,d,e\n");
    	scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); //a=19 b=3 c=23 d=2 e=31
    	printf("前半部分余数为：\n");      
    	printf("%d\n",powMod(a,b,c));      //5
    	printf("总余数为：\n");      
    	printf("%d",powMod(powMod(a,b,c),d,e));  
    	//同理，再此使用powMod函数（a=5,b=2,c=31） 5^2 mod 31=25
    	//此时不符合b%2==1
    	//执行b/=2=>b=1  a=a*a%c=5*5%31=25  
    	
    	//1%2=1  result=1*25%31=25
    	//b/=2 b=0(int)
    	//a=a*a%c=5*5%31=25  
    	//返回值25 
    	return 0;
     }

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关【OJ】数字整除——大数运算之取余

1003: 数字整除题目描述定理：把一个至少两位的正整数的个位数字去掉，再从余下的数中减去个位数的5倍。当且仅当差是17的倍数时，原数也是17的倍数。 ...

我不是女神ヾ/ 2024年04月19日 16:29/ 0 赞/ 95 阅读

相关 K - Large Division（模拟大数取余）

目：K - Large Division LightOJ - 1214 /********** 用字符串模拟大数取余 *************/ i...

桃扇骨/ 2024年04月17日 05:40/ 0 赞/ 71 阅读

相关大数取余运算(详解)

大数取余运算(详解) //(19^3 mod 23)^2 mod 31=25 //a=19 b=3 c=23 d=2 e=31 include<s

缺乏、安全感/ 2023年10月04日 15:45/ 0 赞/ 30 阅读

相关 BigDecimal取余运算

取余运算在编程中运用非常广泛，对于BigDecimal对象取余运算可以通过divideAndRemainder方法实现。 public BigDecimal[] di

迷南。/ 2022年08月20日 11:14/ 0 赞/ 222 阅读

相关取余运算？

取余运算？ Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述取余运算：设x = a%b，则x

以你之姓@/ 2022年08月14日 05:48/ 0 赞/ 248 阅读

相关取余运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下： (a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a

骑猪看日落/ 2022年08月11日 00:50/ 0 赞/ 274 阅读

相关取余运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下： (a + b) % p = (a % p + b % p) % p （1） (a - b) % p

傷城~/ 2022年07月16日 13:48/ 0 赞/ 272 阅读

相关 Java中的取余运算和取模运算

通常取模运算也叫取余运算，他们都遵循处罚法则，返回结果都是余数；但是仔细看是不一样的，详细请看实例： 1.取余 rem(3,2)=1 rem(-3,-2)=-

痛定思痛。/ 2022年06月16日 13:49/ 0 赞/ 840 阅读

相关位运算取余

我们都知道，求一个数被另一个数整除的余数，可以用求余运算符“%”，但是，如果不允许使用求余运算符，又该怎么办呢？下面介绍一种方法，是通过位运算来求余，但是注意：该方法只对除数是

我不是女神ヾ/ 2022年06月02日 05:25/ 0 赞/ 331 阅读

相关大数取余模板

include<stdio.h> include<stdlib.h> include<string.h> int big(int BigNum[

悠悠/ 2022年05月17日 13:19/ 0 赞/ 190 阅读