CodeForces 300C Beautiful Numbers（乘法逆元/费马小定律+组合数公式+快速幂） - 综合当前位置:& &&&CodeForces 300C Beautiful Numbers（乘法逆元/费马CodeForces 300C Beautiful Numbers（乘法逆元/费马小定律+组合数公式+快速幂）&&网友分享于：&&浏览：0次CodeForces 300C Beautiful Numbers（乘法逆元/费马小定理+组合数公式+快速幂）
memory limit per test
256 megabytes
standard input
standard output
Vitaly is a very weird man. He's got two favorite digits&&and&.
Vitaly calls a positive integer&good, if the decimal representation of this integer only contains digits&&and&.
Vitaly calls a good number&excellent, if the sum of its digits is a good number.
For example, let's say that Vitaly's favourite digits are&&and&,
then number&&isn't good and numbers&&or&&are.
Also, number&is excellent and number&&isn't.
Now Vitaly is wondering, how many excellent numbers of length exactly&&are there. As this number can be rather large, he asks you
to count the remainder after dividing it by&& + 7).
A number's length is the number of digits in its decimal representation without leading zeroes.
The first line contains three integers:&,&,&&).
Print a single integer — the answer to the problem modulo&& + 7).
Sample test(s)
题目大意：
给出a和b，如果一个数每一位都是a或b，那么我们称这个数为good，在good的基础上，如果这个数的每一位之和也是good，那么这个数是excellent。求长度为n的excellent数的个数mod(1e9+7)。ps：1e9+7是一个质数。
解题思路：
由于题目中给出了n，所以我们可以枚举a的个数m，那么剩下的（n-m）位就是b。再判断a*m+b*(n-m)是不是good数，如果是，那么我们在答案中加上C(m,n)即可，枚举完毕即最终答案。
但是n最大为1e6，计算组合数时(C(m,n)=n!/(m!*(n-m)!))要计算n的阶乘，直接计算肯定会出现错误。
在这里介绍一些数学知识：
（1）费马小定理
费马小定理(Fermat Theory)是数论中的一个重要定理，其内容为： 假如p是质数，且Gcd(a,p)=1，那么 a(p-1)（mod p）≡1。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。（我爱度娘(╯‵□′)╯︵┻━┻）。
简而言之就是如果a，p互质，同时p是质数，那么a^(p-1) mod p=1。证明略。
（2）乘法逆元
若对于a，p存在x，使得a*x mod p=1，那么我们称x为a对p的乘法逆元。证明略。
那么乘法逆元存在的意义是什么呢？
假如我们要求(a/b) mod p且无法直接求得a/b的值时，我们可以求出b对p的乘法逆元inv，那么(a/b) mod p=(a*inv) mod p。证明略。。。
bazinga！！！
假如inv是b对于p的乘法逆元，即b*inv=p*t+1（t为整数），移项得inv=(p*t+1)/b
(a*inv) mod p
=(a*((p*t+1)/b)) mod p
=(a*(p*t/b+1/b)) mod p
=(a/b) mod p+(a*(p*t+1)) mod p
=(a/b) mod p+(a*p*t/b) mod p
∵ (a*p*t/b) mod p=0
∴ 原式=(a/b) mod p
即(a*inv) mod p=(a/b) mod p
有了这2个概念我们就可以快速地算出组合数了。
我们可以知道x与x^p-2互为逆元（p是质数）。
证明：x与x^(p-2)互为逆元（p是质数）
由费马小定理：x^(p-1) mod p=1
x*(x^(p-2)) mod p=1
得x与x^(p-2)互为乘法逆元，证毕。
由上述结论可知，要计算C(i,n)，即计算n!/(i!*(n-i)!) mod p，那么我们只需要计算n!*(i!*(n-i))^(p-2) mod p。
参考代码：
#include&map&
#include&stack&
#include&queue&
#include&cmath&
#include&vector&
#include&cctype&
#include&cstdio&
#include&cstring&
#include&iostream&
#include&algorithm&
const double eps=1e-10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
const int MAXN=1e6+50;
typedef __int64 LL;
LL f[MAXN],a,b,n;
bool is_excellent(int x)
if(x%10!=a&&x%10!=b)
LL fastmod(LL b,LL c,LL mod)//b^c%mod
LL re=1,base=b;
re=((re%mod)*(base%mod))%
base=((base%mod)*(base%mod))%
return re%
int main()
#ifndef ONLINE_JUDGE
freopen(&in.txt&,&r&,stdin);
#endif // ONLINE_JUDGE
for(int i=2;i&=1e6;i++)
f[i]=(f[i-1]*i)%MOD;
while(scanf(&%I64d%I64d%I64d&,&a,&b,&n)!=EOF)
for(int i=0;i&=n;i++)
int num=a*i+b*(n-i);
if(is_excellent(num))
LL t=f[n];
t=(t*fastmod(f[i],MOD-2,MOD))%MOD;
t=(t*fastmod(f[n-i],MOD-2,MOD))%MOD;
ans=(ans+t)%MOD;
printf(&%I64d\n&,ans%MOD);
版权声明：本文为博主原创文章，未经博主允许不得转载。
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有&&&&&&& SICP第35页提到在密码学中有很重要的应用, 还没有学过&密码学&这门课, 但我又对加密解密有点兴趣, 决定一探究竟. 费马小定理维基百科里是这么定义的:
假如a是一个整数，p是一个素数，那么
如果a不是p的倍数，这个定理也可以写成
&&&&&&& 但我发现SICP第34页对费马小定理的描述是这样的:
如果n是一个素数, a是小于n的任意正整数, 那么a的n次方与a模n同余.
&&&&&&& 经过我举了几个小例子验证之后, 觉得维基百科的解释更合理一些, SICP里所讲的"a是小于n的任意正整数"可能是为了适合当页所讲的内容"费马检查", 顺便提一下如何检查一个数是否是素数.
如果所有符合1 & b & p的b p都满足下列条件的话：
, 则p必定是一个素数. 实际上没有必要检测所有小于p的正整数, 而仅需测试所有的小于p的素数即可.
公钥加密是怎么回事
&&&&&&& 想起前一段时间读过的, 这篇文章里面描述了公钥加密的过程:
1. 找两个很大的素数（质数）P 和 Q, 越大越好, 比如 100 位长的, 然后计算它们的乘积 N=P&Q, M=(P-1)&(Q-1) 2. 找一个和 M 互素的整数 E, 也就是说 M 和 E 除了 1 以外没有公约数 3. 找一个整数 D, 使得 E&D 除以 M 余 1, 即 E&D mod M = 1 现在, 世界上先进的、最常用的密码系统就设计好了, 其中 E 是公钥谁都可以用来加密, D 是私钥用于解密, 一定要自己保存好. 乘积 N 是公开的, 即使敌人知道了也没关系. 现在, 我们用式子 X^E mod N 对 X 加密得到密码 Y, 破解密文时用式子 Y^D mod N 得到原文X.
&&&&&&& 这就相当于可以给每个人发一把钥匙(公钥)用于加密数据, 但是解开这段加密数据需要的是另外一把钥匙(私钥).
&&&&&&& 原文X = Y^D mod N = (X^E mod N)^D mod N, 根据同余定理这个式子等价为: X^(E*D) mod N = X, 目的就是证明这个式子的正确性.
根据费马小定理, 所以X^(E-1) = 1(mod E),
设整数k使得((P-1)(Q-1))k+1=E*D, 所以X^(E*D)=X^((P-1)(Q-1)k+1) = X*X^((P-1)^(Q-1)) = X(mod& P),
同理X^(E*D) = X(mod& Q), 即X^(E*D) & X能被P*Q整除,
因为N=P*Q, 所以X^(E*D) = X(mod N), 即得证.
&&&&&&& 这个加密解密过程也就是RSA公钥密码的原理.
&&&&&&& 费马检查用于检查一个数是否是素数, 根据这个基本原理, 用来找到一个比现在已知素数还要大的素数, 这样的素数在密码学中有什么用呢? 上面公钥加密过程第一步已经提到需要两个很大的素数构造N, 而一旦破解N是由哪两个素数相乘, 整个公钥加密系统也就没有什么秘密了, 但目前还没有发现求一个数的因子的很好算法, 除非一个个试, 但这需要很漫长的时间, 据说分解一个200位的数就得花上上万年...因此可见位数越多的素数乘积起来, 再进一步构造出来的密码, 要破解它是相当困难的.
阅读(...) 评论()