a*b/c 数字很大，不用大数法

Angelice

Description:

       题目非常的简单，输入三正整数ABC，输出(A*B)%C的值。不过这样一句scanf和一句printf就能解决的问题肯定会让这么聪明的你感觉很郁闷的，所在这里加一点点难度，测试数据里的A，B，C的值会稍大一点点，不过最大不会超过2^63。
      或许，你会想用大数做，不过大数的乘和模不是很好写，那有没有其它方法呢。我想，聪明的你很快就想到的 :)
      


Input:

输入多组测试数据，每组一行三个正整数，A，B，C。0 < A , B , C < 263 。



Output:

每个测试数据一行，(A*B)%C的值。



Sample Input:

1 2 10 12 14 100 15 3 21



Sample Output:

2 68 3

Angelice

标题写错了:sweat:       是   a * b % c

Angelice

Input:

输入多组测试数据，每组一行三个正整数，A，B，C。0 < A , B , C < 2 的 63 次 方。
:sweat::sweat::sweat::sweat::sweat::sweat::sweat::sweat:

小甲鱼

1. 
   
2. #include<stdio.h>
   
3. 
   
4. int main()
   
5. {
   
6.         int a,b,c;
   
7. 
   
8.         while ( scanf("%d%d%d",&a,&b,&c)!=EOF && a!=0 && b!=0 && c!=0 )
   
9.         {
   
10.                 int k=1;
    
11.                 while (b>0)
    
12.                 {
    
13.                         if(b&1!=0)     // 作用1：当 b为奇数，则先单独乘一个a
    
14.                                               // 作用：当 b=1时，即 已经乘了 b=b/2=1后，将值赋给k
    
15.                                 k=(k*a)%c;   
    
16.                         a=(a*a)%c;   
    
17.                         b>>=1;         // a1=a%c                                               1=2^0   
    
18.                                              // a2=((a%c)*(a%c))%c                           2=2^1
    
19.                                              // a3=((a%c*a%c)%c*(a%c*a%c)%c)      4=2^2
    
20.                                              // 由此，可知 b=b/2 ,每次的 a 的个数为上一次的 2倍
    
21.                 }
    
22.                 printf("%d\n",k);
    
23.         }
    
24.         return 0;
    
25. }
    

复制代码

Angelice

小甲鱼 发表于 2013-8-1 01:21

                               
登录/注册后可看大图

非常感谢~~  可是为什么我输入5 8 7 输出是4  余数不应该是5么？

晨风吹过

学习了，支持啊

liufei_vip

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         long a,b,c;
   
6.         while(scanf("%d%d%d",&a,&b,&c) != EOF)
   
7.         {
   
8.                 printf("%d\n",((a%c)*(b%c))%c);
   
9.         }
   
10. 
    
11.         return 0;
    
12. }

复制代码

秒杀