1695人阅读
Problem Description
Sample Input
Sample Output
For the second example:
0 express face down,1 express face up
Initial state 000
The first result:000-&111-&001-&110
The second result:000-&111-&100-&011
The third result:000-&111-&010-&101
So, there are three kinds of results(110,011,101)
题意：对于m张牌给出n个操作，每次操作选择a[i]张牌进行翻转，问最终得到几个不同的状态
思路：在n张牌选k张，很容易想到组合数，但是关键是怎么进行组合数计算呢？我们可以发现，在牌数固定的情况下，总共进行了sum次操作的话，其实有很多牌是经过了多次翻转，而每次翻转只有0和1两种状态，那么，奇偶性就出来了，也就是说，无论怎么进行翻牌，最终态无论有几个1，这些1的总数的奇偶性是固定的。
那么我们现在只需要找到最大的1的个数和最小的1的个数，然后再这个区间内进行组合数的求解即可
但是又有一个问题出来了，数据很大，进行除法是一个不明智的选择，但是组合数公式必定有除法
C（n,m） = n!/(m!*(n-m)!)
但是我们知道费马小定理a^(p-1)=1%p
那么a^(p-1)/a = 1/a%p 得到 a^(p-2) = 1/a%p
发现了吧？这样就把一个整数变成了一个分母！
于是便得到sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-2)%mod))%mod
用快速幂去撸吧！
#include &iostream&
#include &stdio.h&
#include &string.h&
#include &algorithm&
#define mod
#define LL __int64
#define maxn
LL f[maxn];
void set()
for(i = 1; i& i++)
f[i] = (f[i-1]*i)%
LL quickmod(LL a,LL b)
LL ans = 1;
ans = (ans*a)%
a = ((a%mod)*(a%mod))%
int main()
int n,m,i,j,k,l,r,x,ll,
while(~scanf(&%d%d&,&n,&m))
l = r = 0;
for(i = 0; i&n; i++)
scanf(&%d&,&x);
//计算最小的1的个数，尽可能多的让1-&0
if(l&=x) ll = l-x;//当最小的1个数大于x，把x个1全部翻转
else if(r&=x) ll = ((l%2)==(x%2))?0:1;//当l&x&=r，由于无论怎么翻，其奇偶性必定相等，所以看l的奇偶性与x是否相同，相同那么知道最小必定变为0，否则变为1
else ll = x-r;//当x&r,那么在把1全部变为0的同时，还有x-r个0变为1
//计算最大的1的个数,尽可能多的让0-&1
if(r+x&=m) rr = r+x;//当r+x&=m的情况下，全部变为1
else if(l+x&=m) rr = (((l+x)%2) == (m%2)?m:m-1);//在r+x&m但是l+x&=m的情况下，也是判断奇偶，同态那么必定在中间有一种能全部变为1，否则至少有一张必定为0
else rr = 2*m-(l+x);//在l+x&m的情况下，等于我首先把m个1变为了0，那么我还要翻（l+x-m）张，所以最终得到m-(l+x-m)个1
l = ll,r =
LL sum = 0;
for(i = i&=r; i+=2)//使用费马小定理和快速幂的方法求和
sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-2)%mod))%
printf(&%I64d\n&,sum%mod);
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：903255次
积分：18587
积分：18587
排名：第210名
原创：1000篇
评论：237条
(14)(8)(76)(44)(47)(17)(2)(2)(35)(18)(40)(36)(27)(13)(39)(49)(59)(32)(69)(77)(35)(61)(71)(71)(11)(44)(9)设p是大于5的质数,求证:p^4≡1(mod240)用费马小定理和欧拉定理知识求解,急,收到请速回复谢谢!_百度作业帮
设p是大于5的质数,求证:p^4≡1(mod240)用费马小定理和欧拉定理知识求解,急,收到请速回复谢谢!
设p是大于5的质数,求证:p^4≡1(mod240)用费马小定理和欧拉定理知识求解,急,收到请速回复谢谢!
证明：欲证p^4≡1(mod240),即证：240|(p^4-1)
∵240=3*5*2^4
（1）∵p为大于5的质数,∴(p, 5)=1,∴由费马定理：p^4≡1(mod5)
∴5|(p^4-1)
（2）∵p为大于5的质数,∴(p, 3)=1,∴由费马定理：p^2≡1(mod3)
又p^4-1=(p^2+1)(p^2-1),∴3|(p^4-1)
（3）∵p为大于5的质数,∴p为奇数
∴p=4k+1或4k+3
当p=4k+1时,p^4-1=(p^2+1)(p+1)(p-1)
∵p-1=4k,∴4|(p-1),而p为奇数,∴p^2+1, p+1均为偶数
∴4|(p^2+1)(p+1),∴16|(p^2+1)(p+1)(p-1),即16|(p^4-1)
当p=4k+3时,p^4-1=(p^2+1)(p+1)(p-1)
∵p+1=4k+4,∴4|(p+1),而p为奇数,∴p^2+1, p-1均为偶数
∴4|(p^2+1)(p-1),∴16|(p^2+1)(p+1)(p-1),即16|(p^4-1)
综上,16|(p^4-1)成立!
∴综合(1)、(2)、(3)可得：240|(p^4-1)
∴p^4≡1(mod240)望采纳!有问题请追问!关于同余问题.求教./question/.html?si=1 关于这道题.这里面的最佳答案中的3^38=3^32*3^6≡1*9*(-4)≡15(mod17) 不理解.因为完全是刚接触.希望详细的解释._百度作业帮
关于同余问题.求教./question/.html?si=1 关于这道题.这里面的最佳答案中的3^38=3^32*3^6≡1*9*(-4)≡15(mod17) 不理解.因为完全是刚接触.希望详细的解释.
关于同余问题.求教./question/.html?si=1 关于这道题.这里面的最佳答案中的3^38=3^32*3^6≡1*9*(-4)≡15(mod17) 不理解.因为完全是刚接触.希望详细的解释.
从你提到的问题那里复制了一些文字,作了重排.以下也用==代替≡.题：解释 3^38=3^32*3^6≡1*9*(-4)≡15(mod17) 答：a≡b(modm),c≡d(modm) 则ac≡bd(modm)推论：a≡b(modm),则a^n≡b^n(modm).(即同余式两端取乘幂仍成立)利用以上知识得到：3^2≡9(mod17),(两边平方得下一式,以下类似)3^4≡81≡-4(mod17)3^8≡16≡-1(mod17)3^16≡1(mod17)如果利用费马小定理,可以立即得到3^16≡1(mod17)于是：3^38==3^32*3^6≡1*9*(-4)≡15(mod17) 其中3^32==(3^16)^2==1^2==1; 3^6==(3^2)*(3^4)==9*(-4)==-2==15注：费马小定理：质数p不整除a,则：a^(p-1)≡1(modp)附：对于非素数模(除数)m求余,还要用到费马小定理的推广：欧拉函数定理：(a,m)=1,则a^φ(m)=1 mod mφ(m)是欧拉函数,是不大于m且与m互素的正整数的个数.比如：3^406 mod 14小于14与14互质的自然数有6个(可以列举出来1,3,5,9,11,13；复杂的m有公式计算这个个数φ(m)),即φ(14)=6于是：3^6==1 mod 14.而406=6k+4故3^406==3^4==81==11 mod 14.己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x用费马小定理和欧拉定理的知识求解,急.收到请速回复谢谢_百度作业帮
己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x用费马小定理和欧拉定理的知识求解,急.收到请速回复谢谢
己知a=18,m=77,求使a^x≡1(mod m)成立的最小自然数x用费马小定理和欧拉定理的知识求解,急.收到请速回复谢谢
欧拉定理(a,m)=1,则a^φ(m)≡1 (mod m)我们可以把77分成7×11来考虑,即找使18^y≡1(mod 7)和18^z≡1(mod 11)的最小自然数y和z.由欧拉定理可得18^6≡1 (mod 7) 和18^10≡1 (mod 11)18≡4(mod 7),则4^6≡1(mod 7),6=2×3,易验证4^3≡1(mod 7),则18^3≡1(mod 7)y最小为3.18≡7(mod 11),则7^10≡(mod 7),10=2×5,易验证7^2和7^5模11均不为1,所以z最小为10.综合两者,3和10的最小公倍数为30,所以最小的x为30.18^30≡1(mod 77)
则4^6≡1(mod 7)怎么来的，能说清楚些吗?我看不明白，急，收到请速回复谢谢！
4和7互素，由欧拉定理可得4^φ(7)≡1 (mod 7)
由于7为素数所以φ(7)=6.
后面我有地方打错了，是：
”18≡7(mod 11)，则7^10≡1(mod 11)，10=2×5，易验证7^2和7^5模11均不为1“
这里也是欧拉定理φ(11)=10求求算下：解同余式f(x)≡3x^14+4x^13+2x^11+x^9++x^6+x^3+12x^2+x≡0(mod5)._百度作业帮
求求算下：解同余式f(x)≡3x^14+4x^13+2x^11+x^9++x^6+x^3+12x^2+x≡0(mod5).
求求算下：解同余式f(x)≡3x^14+4x^13+2x^11+x^9++x^6+x^3+12x^2+x≡0(mod5).
首先,x==0 mod 5是一解；当x0 mod 5 时,由欧拉函数定理或费马小定理,x^4==1 mod 5,此时f(x)==3x^2 + 4x + 2x^3 + x + x^2 + x^3 + 12x^2 + x=(3+1+12)xx+(4+1+1)x+(2+1)xxx==xx+x+3xxx=x(3xx+x+1)==0 mod 5由于x0　mod 5,故 3xx+x+1==0 mod 5故6xx+2x+2==0==xx+2x+2故(x+1)^2==-1 mod 5故x==1,2 mod 5综上,x==0,1,2 mod 5