计算数论，hdu 3123（GCC）数论

2023-09-28 阅读 19 评论 0

摘要：http://acm.hdu.edu.cn/showproblem.php?pid=3123 题目给出的n很大，很明显如果n很大时，是不用处理到n的，所以其中必有蹊跷！当n大于m时，n的阶乘中必定包含因数m，所以取余后必定为0；这是本体的关键。 View Code 1 #incl

http://acm.hdu.edu.cn/showproblem.php?pid=3123

题目给出的n很大，很明显如果n很大时，是不用处理到n的，所以其中必有蹊跷！

当n大于m时，n的阶乘中必定包含因数m，所以取余后必定为0；这是本体的关键。

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     __int64 ans,sum,temp,max;
 6     char str[150];
 7     int t,m,len;
 8     int i;
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%s",str);
13         scanf("%d",&m);
14         len=strlen(str);
15         if(len>=7)
16         {
17             max=m;
18         }
19         else
20         {
21             max=0;
22             for(i=0;i<len;i++)
23              max=max*10+str[i]-'0';
24         }
25         ans=temp=1;
26         for(i=1;i<=max;i++)
27         {
28             temp=temp*i%m;
29             ans=(ans+temp)%m;
30         }
31         printf("%I64d\n",ans%m);
32     }
33     return 0;
34 }