取模演算法

㈠ c#中的取模演算法是什麼意思

等於1
c語言中的取模運算就是一個取余數的過程。常用%號表示取模運算。可以將取模運算看成取余運算。
10÷3=3....1 10除3的余數為1 ，在C語言中10取模3的結果也為1。兩者在處理的效果上沒任何差別。只不過一個是數學運算，一個是編程語言中的一種運算方式。
取模運算常用在判斷素數，判斷奇偶數，判斷最大公約數中較為常用，一般作為判斷依據。
(1)取模演算法擴展閱讀：
給定一個正整數p，任意一個整數n，一定存在等式 ：
n = kp + r ；
其中 k、r 是整數，且 0 ≤ r < p，則稱 k 為 n 除以 p 的商，r 為 n 除以 p 的余數。
對於正整數 p 和整數 a,b，定義如下運算：
取模運算：a % p（或a mod p），表示a除以p的余數。
模p加法： ，其結果是a+b算術和除以p的余數。
模p減法： ，其結果是a-b算術差除以p的余數。
模p乘法： ，其結果是 a * b算術乘法除以p的余數。

㈡ php中的取模的演算法

演算法是

90 / 22 = 4
余數是 4 所以 90對22取模之後的結果就是 4 也就是倆數相除的余數

90/22後得出4，然後再拿22乘以4得出88，再拿90減去88等於2

㈢ 單片機中取模什麼意思

1、取模就是除法結果取整數的部分
比如21除以7
的模就是3，,22除以7的模也是3，取模和取余是相對的，取余就是除了整除部分的余數，比如21除以7模是3，取余就是0，22除以7取模為3，取余就是1，在單片機中也只是利用數學知識和變數來建立一個能夠實現目的的模式；
2、單片機中還有取余演算法：就是整數x被整數y除後的余數，例如：
int
i,j,k;
j=i/10;
k=i%10;
假如i=78,則j=7,k=8;k就是i除以10的余數。

㈣ 求一個高效的指數取模運算演算法

由於一個整數的指數結果很大，可能遠遠超出計算機處理范圍，故必須簡化計算方式．這里採用快速取模方法.原理為：在4的5次方運算中，5能夠化作2*2+1，這是因為5的2進制數為101．所以4的5次方運算便能寫作((4)^2*1)^2*4,其中1表示的是4的0次方，^2表平方．再運用模的性質：(a*b)mod(m)=(amod(m)*bmod(m))mod(m),所以（4^5）mod(m)可先化為（((4)^2*1)^2*4）mod(m)，再化為（((4)^2mod(m)*1)^2mod(m)*4）mod(m)．舉例子－－（4^5）mod(3)＝（((4)^2*1)^2*4）mod(3)＝（(1*1)^2mod(3)*4）mod(3)=（1*4）mod(3)＝1．該函數運行方式取於上述演算法思想，首先將冪分解成2進制數，得到一個從冪的最低位數開始01組成的棧：分解b為2進制數．記錄下分解成的位數z，構造棧
for(;b!=1;b>>=1)
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;｝
然後出棧進行＂（a^b）mod(c)＂的運算．這里用棧的原因是為了使冪的2進制數排列倒過來，實現最高位上的2進制數能夠循環它的位數次，最低位上的2進制數只循環一次．每次的循環得到平方取模的值，一直到結束，取得一個值，即（a^b）mod(c)．
for(;z>0;z--)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最後次模
return y;
這是一個比較快的運算方法.
完整源程序：
//指數取模:a的b次方modc=x
_int64 mod(_int64 a,_int64 b,_int64 c)//(a)^bmod(c)//條件1：在rsa中a<c,其它不用a<c.條件2:ac互素
{
_int64 l[500],z=-1,y;
for(;b!=1;b>>=1)//分解b為2進制數．記錄下分解成的位數z，構造棧l
{
z++;
if(b%2==0) l[z]=0;
else l[z]=1;
}
//a%=c;//如果一開始數就很大，先模一次,防止過大, 求逆
y=a*a%c;//第一次模
for(;z>0;z--)
{
if(l[z]) y=(y*a%c)*(y*a%c)%c;
else y=y*y%c;
}
if(l[0]) y=(y*a%c);//最後次模
return y;
}

C#改寫的，在vs.net 2005下調試通過：
/// <summary>
/// 指數取模:x=(a^b)%c （a的b次方mod）
/// 條件1：在rsa中a<c,其它不用a<c
/// 條件2:ac互素
/// </summary>
private static long mod(long a, long b, long c)
{
long[] l = new long[500];
long z = -1, y;
for (; b != 1; b >>= 1)//分解b為2進制數．記錄下分解成的位數z，構造棧l
{
z++;
if (b % 2 == 0)
l[z] = 0;
else
l[z] = 1;
}
//a%=c;//如果一開始數就很大，先模一次,防止過大, 求逆
y = a * a % c;//第一次模
for (; z > 0; z--)
{
if (l[z]>0) y = (y * a % c) * (y * a % c) % c;
else y = y * y % c;
}
if (l[0]>0) y = (y * a % c);//最後次模
return y;
} (參考網路）

㈤ c語言如何取模運算

取模運算：a % p（或a mod p），表示a除以p的余數。

比如給定一個正整數p，任意一個整數n，一定存在等式 ：n = kp + r ；其中 k、r 是整數，且 0 ≤ r < p，則稱 k 為 n 除以 p 的商，r 為 n 除以 p 的余數。

取模運算的規則如下：

1、(a + b) % p = (a % p + b % p) % p 。

2、(a - b) % p = (a % p - b % p) % p 。

3、(a * b) % p = (a % p * b % p) % p 。

4、a ^ b % p = ((a % p)^b) % p 。

(5)取模演算法擴展閱讀：

模運算與基本四則運算有些相似，但是除法例外。其規則如下：

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

a ^ b % p = ((a % p)^b) % p （4）

結合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

((a*b) % p * c)% p = (a * (b*c) % p) % p （6）

交換律：

(a + b) % p = (b+a) % p （7）

(a * b) % p = (b * a) % p （8）

分配律：

(a+b) % p = ( a % p + b % p ) % p （9）

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （10）

參考資料：網路-取模運算

㈥ 取模是怎麼運算的希望可以講通俗一點

對於整型數a，b來說，取模運算或者求余運算的方法都是：

1、求整數商： c = [a/b]；

2、計算模或者余數： r = a - c×b。

求模運算和求余運算在第一步不同，取余運算在取c的值時，向0 方向舍入(fix()函數)；而取模運算在計算c的值時，向負無窮方向舍入(floor()函數)。

(6)取模演算法擴展閱讀：

取模運算重要定理：

1、若a≡b (% p)，則對於任意的c，都有(a + c) ≡ (b + c) (%p)。

2、若a≡b (% p)，則對於任意的c，都有(a * c) ≡ (b * c) (%p)。

3、若a≡b (% p)，c≡d (% p)，則 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，(a * c) ≡ (b * d) (%p)。

㈦ 取模運算的應用

奇偶數的判別是模運算最基本的應用，也非常簡單。
已知一個整數n對2取模，如果余數為0，則表示n為偶數，否則n為奇數。
C++實現功能函數： /*函數名：IsEven函數功能：判別整數n的奇偶性。能被2整除為偶數，否則為奇數輸入值：intn，整數n返回值：bool，若整數n是偶數，返回true，否則返回false*/boolIsEven(intn){return(n%2==0);} 一個數，如果只有1和它本身兩個因數，這樣的數叫做質數（或素數）。例如 2，3，5，7 是質數，而 4，6，8，9 則不是，後者稱為合成數或合數。
判斷某個自然數是否是素數最常用的方法就是試除法——用比該自然數的平方根小的正整數去除這個自然數，若該自然數能被整除，則說明其非素數。
C++實現功能函數：
/*函數名：IsPrime函數功能：判別自然數n是否為素數。輸入值：intn，自然數n返回值：bool，若自然數n是素數，返回true，否則返回false*/
bool IsPrime(unsignedintn)
{
unsigned maxFactor=sqrt(n);//n的最大因子
for(unsignedinti=2;i<=maxFactor;i++)
{
if(n%i==0)//n能被i整除，則說明n非素數
{
returnfalse;
}
}
return true;
}求最大公約數
求最大公約數最常見的方法是歐幾里德演算法（又稱輾轉相除法），其計算原理依賴於定理：gcd(a,b) = gcd(b,a mod b)
證明：
a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。
C++實現功能函數：
/*函數功能：利用歐幾里德演算法，採用遞歸方式，求兩個自然數的最大公約數函數名：Gcd輸入值：unsigned int a，自然數a；unsigned int b，自然數b返回值：unsigned int，兩個自然數的最大公約數*/
unsigned int Gcd(unsigned int a,unsigned int b)
{
if(b==0)
return a;
return Gcd(b,a%b);
}/*函數功能：利用歐幾里德演算法，採用迭代方式，求兩個自然數的最大公約數函數名：Gcd輸入值：unsigned int a，自然數a；unsigned int b，自然數b返回值：unsigned int，兩個自然數的最大公約數*/
unsigned int Gcd(unsigned int a,unsigned int b)
{
unsigned int temp;
while(b!=0)
{
temp=a%b;
a=b;
b=temp;
}
returna;
}模冪運算
利用模運算的運算規則，我們可以使某些計算得到簡化。
例如，我們想知道3333^5555的末位是什麼。很明顯不可能直接把3333^5555的結果計算出來，那樣太大了。但我們想要確定的是3333^5555（%10），所以問題就簡化了。
根據運算規則（4）a^b % p = ((a % p)^b) % p ，我們知道3333^5555（%10）= 3^5555（%10）。由於3^4 = 81，所以3^4（%10）= 1。
根據運算規則（3） (a * b) % p = (a % p * b % p) % p ，由於5555 = 4 * 1388 + 3，我們得到3^5555（%10）=（3^(4*1388) * 3^3）（%10）=（（3^(4*1388)（%10）* 3^3（%10））（%10）
=（1 * 7）（%10）= 7。
計算完畢。
利用這些規則我們可以有效地計算X^N(% P)。簡單的演算法是將result初始化為1，然後重復將result乘以X，每次乘法之後應用%運算符（這樣使得result的值變小，以免溢出），執行N次相乘後，result就是我們要找的答案。
這樣對於較小的N值來說，實現是合理的，但是當N的值很大時，需要計算很長時間，是不切實際的。下面的結論可以得到一種更好的演算法。
如果N是偶數，那麼X^N =（X*X）^[N/2]；
如果N是奇數，那麼X^N = X*X^(N-1) = X *（X*X）^[N/2]；
其中[N]是指小於或等於N的最大整數。
C++實現功能函數：
/*函數功能：利用模運算規則，採用遞歸方式，計算X^N(%P)函數名：PowerMod輸入值：unsigned int x，底數x unsigned int n，指數nunsigned int p，模p返回值：unsigned int，X^N(%P)的結果*/
unsignedintPowerMod(unsignedintx,unsignedintn,unsignedintp)
{
if(n==0)
{
return1;
}
unsignedinttemp=PowerMod((x*x)%p,n/2,p);//遞歸計算（X*X）^[N/2]
if((n&1)!=0)//判斷n的奇偶性
{
temp=(temp*x)%p;
}
returntemp;
}
《孫子問題(中國剩餘定理)》
在我國古代算書《孫子算經》中有這樣一個問題：
「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」意思是，「一個數除以3餘2，除以5餘3，除以7餘2.求適合這個條件的最小數。」
這個問題稱為「孫子問題」.關於孫子問題的一般解法，國際上稱為「中國剩餘定理」.
我國古代學者早就研究過這個問題。例如我國明朝數學家程大位在他著的《演算法統宗》（1593年）中就用四句很通俗的口訣暗示了此題的解法：
三人同行七十稀，五樹梅花甘一枝，七子團圓正半月，除百零五便得知。
正半月暗指15。除百零五的原意是，當所得的數比105大時，就105、105地往下減，使之小於105；這相當於用105去除，求出余數。
這四句口訣暗示的意思是：當除數分別是3、5、7時，用70乘以用3除的余數，用21乘以用5除的余數，用15乘以用7除的余數，然後把這三個乘積相加。加得的結果如果比105大，就除以105，所得的余數就是滿足題目要求的最小正整數解。
根據剩餘定理，我把此種解法推廣到有n(n為自然數）個除數對應n個余數，求最小被除數的情況。輸入n個除數（除數不能互相整除）和對應的余數，計算機將輸出最小被除數。
C++實現功能函數：
/*函數名：ResieTheorem函數功能：運用剩餘定理，解決推廣了的孫子問題。通過給定n個除數（除數不能互相整除）和對應的余數，返回最小被除數輸入值：unsignedintdevisor[]，存儲了n個除數的數組unsignedintremainder[]，存儲了n個余數的數組intlength，數組的長度返回值：unsignedint，最小被除數*/unsignedintResieTheorem(constunsignedintdevisor[],constunsignedintremainder[],intlength){unsignedintproct=1;//所有除數之乘積for(inti=0;i<length;i++)//計算所有除數之乘積{proct*=devisor[i];}//公倍數數組，表示除該元素（除數）之外其他除數的公倍數unsignedint*commonMultiple=newunsignedint(length);for(inti=0;i<length;i++)//計算除該元素（除數）之外其他除數的公倍數{commonMultiple[i]=proct/devisor[i];}unsignedintdividend=0;//被除數，就是函數要返回的值for(inti=0;i<length;i++)//計算被除數，但此時得到的不是最小被除數{unsignedinttempMul=commonMultiple[i];//按照剩餘理論計算合適的公倍數，使得tempMul%devisor[i]==1while(tempMul%devisor[i]!=1){tempMul+=commonMultiple[i];}dividend+=tempMul*remainder[i];//用本除數得到的余數乘以其他除數的公倍數}delete[]commonMultiple;return(dividend%proct);//返回最小被除數}凱撒密碼
凱撒密碼（caeser）是羅馬擴張時期朱利斯·凱撒（Julius Caesar）創造的，用於加密通過信使傳遞的作戰命令。
它將字母表中的字母移動一定位置而實現加密。注意26個字母循環使用，z的後面可以堪稱是a。
例如，當密匙為k = 3，即向後移動3位時，若明文為」How are you!」，則密文為」Krz h btx!」。
凱撒密碼的加密演算法極其簡單。其加密過程如下：
在這里，我們做此約定：明文記為m，密文記為c，加密變換記為E(key1,m)（其中key1為密鑰），
解密變換記為D(key2,m)（key2為解密密鑰）（在這里key1=key2,不妨記為key）。
凱撒密碼的加密過程可記為如下一個變換：c≡m+key (mod n） （其中n為基本字元個數）
同樣，解密過程可表示為：m≡c+key (mod n） （其中n為基本字元個數）
C++實現功能函數：
/*函數功能：使用凱撒密碼原理，對明文進行加密，返回密文函數名：Encrypt輸入值：constcharproclaimedInWriting[]，存儲了明文的字元串charcryptograph[]，用來存儲密文的字元串intkeyey，加密密匙，正數表示後移，負數表示前移返回值：無返回值，但是要將新的密文字元串返回*/voidEncrypt(constcharproclaimedInWriting[],charcryptograph[],intkey){constintNUM=26;//字母個數intlen=strlen(proclaimedInWriting);for(inti=0;i<len;i++){if(proclaimedInWriting[i]>='a'&&proclaimedInWriting[i]<='z'){//明碼是大寫字母，則密碼也為大寫字母cryptograph[i]=(proclaimedInWriting[i]-'a'+key)%NUM+'a';}elseif(proclaimedInWriting[i]>='A'&&proclaimedInWriting[i]<='Z'){//明碼是小寫字母，則密碼也為小寫字母cryptograph[i]=(proclaimedInWriting[i]-'A'+key)%NUM+'A';}else{//明碼不是字母，則密碼與明碼相同cryptograph[i]=proclaimedInWriting[i];}}cryptograph[len]='';}
/*函數功能：使用凱撒密碼原理，對密文進行解密，返回明文函數名：Decode輸入值：charproclaimedInWriting[]，用來存儲明文的字元串constcharcryptograph[]，存儲了密文的字元串intkeyey，解密密匙，正數表示前移，負數表示後移（與加密相反）返回值：無返回值，但是要將新的明文字元串返回*/voidDecode(constcharcryptograph[],charproclaimedInWriting[],intkey){constintNUM=26;//字母個數intlen=strlen(cryptograph);for(inti=0;i<len;i++){if(cryptograph[i]>='a'&&cryptograph[i]<='z'){//密碼是大寫字母，則明碼也為大寫字母，為防止出現負數，轉換時要加個NUMproclaimedInWriting[i]=(cryptograph[i]-'a'-key+NUM)%NUM+'a';}elseif(cryptograph[i]>='A'&&cryptograph[i]<='Z'){//密碼是小寫字母，則明碼也為小寫字母proclaimedInWriting[i]=(cryptograph[i]-'A'-key+NUM)%NUM+'A';}else{//密碼不是字母，則明碼與明密相同proclaimedInWriting[i]=cryptograph[i];}}proclaimedInWriting[len]='';}
模運算及其簡單應用就先講到這了，其實模運算在數學及計算機領域的應用非常廣泛，我這這里搜集整理了一些最最基本的情形，希望能夠起到一個拋磚引玉的作用，讓更多的人關注模運算，並及其應用到更廣闊的領域中。

㈧ C語言，取模演算法，求詳解

比如有個數是123456秒
第一步算之後LedBuff[0] = 6，即123456 % 10 = 6

第二句算完了LedBuff[1] = 5，即123456/10 %10 = 12345 % 10 = 5

依次類推即可。

㈨ 怎樣求大組合數（取模）（ACM演算法）

這種題目然做過的，
意思比較簡單，就由 m 個共 0 和 n 個 1 組成一個串，但從左到右要1出現的次數不少於0出現的次數。
由大牛的演算法： 結果就是 C(m+n, n) - C(m+n, m-1) 再取模，我們可以對式子化簡一下就是：
(n+m)！*
(n-m+1) / ((m)！* (n+1)！)
再取模，但由於組合數很大，直接用大數乘除就會超時了，看了別人的報告才知道原來可以用素數化簡快速求模的， n! = 2^p[i] *
3^p[i] * 5^p[i]*...... 再求模就可以很快了~(^ = ^)~。。。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000], p[150000], len; // prime 記錄素數， p 記錄素數的冪 len 記錄長度
void getprime() // 篩法找素數
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; i<=M; i+=2)
{
if( !sig[i] )
{
prime[k++] = i;
for(j=i; j<=M; j+=i)
sig[j] = 1;
}
}
}
void get(int k, int s) // K! 的素數分解, S為指數的加減(分母，分子)
{
int i, mid;
for(i=0; prime[i]<=k && prime[i]; i++)
{
mid = k;
while(mid)
{
if(s)
p[i] += mid/prime[i];
else
p[i] -= mid/prime[i];
mid /= prime[i];
}
}
if(len < i)
len = i;
}
__int64 cal() // 計算結果 (prime[i...]^p[i...]) % mm
{
__int64 i,ans = 1;
for(i=0; i<=len; i++)
{
if( p[i] )
{
__int64 t = prime[i], b = p[i], ret = 1;
while(b) //計算 (t^b) % mm
{
if(b%2) ret *= t %mm;
t = t*t%mm;
b /= 2;
}
ans = ( ans*ret ) % mm;
}
}
return ans;
}
int main()
{
int t,m,n,i,mid;
__int64 ans;
getprime();
cin>>t;
while(t--)
{
cin>>n>>m;
len = 0;
memset(p, 0, sizeof(p));
mid = n-m+1; //先前要把 n-m+1 的因子加進 P 中去才能使 (m+n)! / ((m)!*(n+1)!) 整除
for(i=0; mid>1; i++)
{
if( mid%prime[i] == 0)
{
while(mid%prime[i]==0)
{
p[i] += 1;
mid /= prime[i];
}
}
}
get(m+n, 1);
get(m, 0);
get(n+1, 0);
ans = cal();
printf("%I64d\n", ans);
}
return 0;
}

可以用素數分解法，
先求出上面和下面的素數表示，然後約分後，再用求冪公式