HDU 3123 GCC (取模运算)

2019-04-14 08:36发布

站内文章 / 模拟电子
16868 0 986
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3123
求0到n的各项的阶乘和对m取模。
思路：根据取模运算性质，(a * b) % p = (a % p * b % p) % p 和 ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p  当n>=m时，第n项阶乘对m取模为0。得到这样暴力解决之。 注意： 1.阶乘要用递推求； 2.输入要用字符串
AC代码：
#include #include #define ll __int64 int main() { ll t,i,m; ll len; char s[1100]; while(scanf("%I64d",&t)!=EOF) { while(t--) { scanf("%s %I64d",s,&m); len=strlen(s); ll temp=0,t=1; for(i=len-1;i>=0;i--) { temp+=(s[i]-'0')*t; t=t*10; if(temp>=m) break; } if(temp<=1) { printf("%I64d ",(temp+1)%m); continue; } ll sum=2,s=1; for(i=2;i<=temp && i<=m;i++) //temp 和m取个最小 { s*=i%m; s%=m; sum+=s%m; sum%=m; } printf("%I64d ",sum%m); } } return 0; }

热门文章