Angelice 发表于 2013-8-1 00:12:57

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

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 发表于 2013-8-1 00:36:10

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

Angelice 发表于 2013-8-1 00:38:31

Input:

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


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


#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-4 12:35:26

小甲鱼 发表于 2013-8-1 01:21 static/image/common/back.gif


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

晨风吹过 发表于 2013-8-15 08:28:54

学习了，支持啊

liufei_vip 发表于 2013-8-21 20:51:10

#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;
}秒杀{:5_103:}
页: [1]
查看完整版本: a*b/c 数字很大，不用大数法