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:

小甲鱼

#include<stdio.h>

int main()
{
        int a,b,c;

        while ( scanf("%d%d%d",&a,&b,&c)!=EOF && a!=0 && b!=0 && c!=0 )
        {
                int k=1;
                while (b>0)
                {
                        if(b&1!=0)     // 作用1：当 b为奇数，则先单独乘一个a 
                                              // 作用：当 b=1时，即 已经乘了 b=b/2=1后，将值赋给k 
                                k=(k*a)%c;   
                        a=(a*a)%c;    
                        b>>=1;         // a1=a%c                                               1=2^0   
                                             // a2=((a%c)*(a%c))%c                           2=2^1
                                             // a3=((a%c*a%c)%c*(a%c*a%c)%c)      4=2^2
                                             // 由此，可知 b=b/2 ,每次的 a 的个数为上一次的 2倍 
                }
                printf("%d\n",k);
        }
        return 0;
}

Angelice

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

                               
登录/注册后可看大图

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

晨风吹过

学习了，支持啊

liufei_vip

#include <stdio.h>

int main()
{
        long a,b,c;
        while(scanf("%d%d%d",&a,&b,&c) != EOF)
        {
                printf("%d\n",((a%c)*(b%c))%c);
        }

        return 0;
}

秒杀