(a*b)%c問題

　
二つの数をあげるint 64型の整数a,b,c.あなたに闻いて、(a*b)%cの値はいくらですか??我々は,(a*b)%c=((a%c)*(b%c))%cを知っている.しかし、それでもcが大きい場合、(a%c)*(b%c)は境界を越えます.次に、バイナリの実装コードを示します.
　　

 1 #include<cstdio>

 2 #include<cstring>

 3 using namespace std;

 4 

 5 __int64 Pow(__int64 a, __int64 b, __int64 c)

 6 {

 7     a %= c;

 8     b %= c;

 9     __int64 ret = 0;   //  (a*b)%c  。

10     while(b)

11     {

12         if(b&1)

13             ret += a, ret %= c;

14         a <<= 1; a %= c;  //a  b               。

15         b >>= 1;  //b                          ，

16     }

17     return ret;

18 }

19 

20 int main()

21 {

22     __int64 a, b, c;

23     while(~scanf("%I64d%I64d%I64d", &a, &b, &c))

24     {

25         printf("%I64d
", Pow(a, b, c));

26     }

27     return 0;

28 }