引言
數論大法好，人間真善美。。。
數論模闆
一. 判定質數
二. 歐拉篩法
三. 歐拉函數
方法一
方法二
四. 二進制一次不定方程
五. 矩陣乘法
六. 快速幂
七. 中國剩餘定理
八. 中國剩餘定理Pro
練習題
一. 判定質數
for(int i = 2 ; i * i <= n ; ++ｉ) ｛
if( n % i == 0 )
{
flag = 1 ;
breke;
}
｝
二. 歐拉篩法
求 n 以内的質數
for(int i = 2 ; i <= n ; ++ i ) {
if( ! vis[i] )
{
cnt ++ ;
p[cnt] = i ;
}
for( int j = 1 ; j <= cnt && i * p[j] <= n ; ++ j )
{
vis[p[j] * i ] = 1 ;
if( i % p[j] == 0 ) break;
}
}
三. 歐拉函數
關于歐拉函數，求 n 以内與 n 互質數的個數
方法一
scanf("%lld", &n );
if( n == 0 )
return 0;
long long m = n ;
for(int i = 2 ; i * i <= m ; ++ i )//分解為質數乘積
{
if( m % i == 0 )
{
cnt ++ ;
p[cnt] = i ;
while( m % i == 0 )
{
m = m / i ;
w[cnt] ++ ;
}
}
}
if( m != 1 )
{
cnt ++ ;
p[cnt] = m ;
w[cnt] = 1 ;
}
long long ans = 1 ;
for(int i = 1 ; i <= cnt ; ++ i )
{
ans = ans * (p[i] - 1 ) ;
for(int j = 1 ; j < w[i] ; j ++ )
{
ans = ans *p[i] ;
}
}
方法二
ph[1] = 1 ;//結合歐式篩法，可以求出 n 以内每一個數的歐拉函數值
scanf("%d", &n );
for(int i = 2 ; i <= n ; ++ i ) {
if(!vis[i]) {
cnt ++ ;
pr[cnt] = i ;
ph[i] = i - 1 ;
}
for(int j = 1 ; j <= cnt && i * pr[j] <= n ; ++ j ) {
vis[ i * pr[j] ] = 1 ;
if( i % pr[j] == 0 ) {
ph[ pr[j] * i ] = ph[i] * pr[j] ;
break;
}
else
ph [ pr[j] * i] = ph[i] * (pr[j] - 1 );
}
}
四. 二進制一次不定方程
關于求解二進制一次不定方程
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int a , b , c , T ;
int ex( int a , int b , int &x , int &y )
{
if( b == 0 )
{
x = 1 ;
y = 0 ;
return a;
}
else
{
int u = ex( b , a % b , y , x );
y -= x *( a/b );
return u ;
}
}
int main()
{
scanf("%d", &T );
for(int h = 1 ; h <= T ; ++ h )
{
scanf("%d%d%d", &a , &b ,&c );
int x = 0 ,y = 0 ;
int p = ex( a, b , x , y );
x = x * ( c / p );
y = y * ( c / p );
cout<<x << " "<< y <<endl;
}
}
五. 矩陣乘法
對于 n*m 的矩陣乘 m*q 的矩陣得到的矩陣為 n*q 的矩陣
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
ll m , n , q ;
ll c[107][107] , a[107][107] , b[107][107] ;
int main()
{
scanf("%lld%lld", &n , & m );
for(int i = 1 ; i <= n ; ++ i )
for(int j = 1 ; j <= m ; ++ j )
scanf("%lld", &a[i][j] );
scanf("%lld", &q );
for(int i = 1 ; i <= m ; ++ i )
for(int j = 1 ; j <= q ; ++ j )
scanf("%lld", &b[i][j] );
for(int i = 1 ; i <= n ; ++ i )
for(int j = 1 ; j <= q ; ++ j )
for(int k = 1 ; k <= m ; ++ k )
c[i][j] += a[i][k] * b[k][j] ;
for(int i = 1 ; i <= n ; ++ i ) {
for(int j = 1 ; j <= q ; ++ j ) {
printf("%lld", c[i][j] );
if( j != q )
printf(" ");
}
printf("\n");
}
return 0;
}
最好用結構體表示矩陣，用構造函數
struct squr{
ll n , m ;
ll c[1007][1007] ;
squr () {
memset( c , 0 , sizeof( c ) );
}
squr operator *( const squr b ) {
squr z;
z.n = n , z.m = b.m ;
for( int i = 1 ; i <= n ; ++ i )
for(int j = 1 ; j <= z.m ; ++ j )
for(int k = 1 ; k <= m ; ++ k )
z.c[i][j] = (z.c[i][j] + ( c[i][k] * b.c[k][j] % mod )) % mod ;
return z ;
}
};
六. 快速幂
x 表示底數，y 是指數,求的是
int quick_pow( int x , int y )
{
int sum = 1 ;
while( y > 0 ) {
if( y % 2 )
sum = sum * x % mod ;
y /= 2;
x = x * x % mod ;
}
return sum;
}
七. 中國剩餘定理
概念（簡化版）
證明（詳細）
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[1007] , m[1007] ;
int n , ans , M =1 ;
int exgcd( int a , int b , int &x , int &y ) //擴充歐幾裡得
{
if( b ==0 ) {
x = 1;
y = 0;
return a;
}
else {
int u = exgcd( b , a%b , y , x );
y -= (a/b)*x ;
return u;
}
}
void China()
{
for(int i = 1 ; i <= n ; ++ i ) {
int temp = M / a[i] ;
int x , y ;
int gcd = exgcd( temp , a[i] , x , y );
x = (x%a[i]+a[i])%a[i] ;
ans = (ans + temp*x*m[i] ) % M ;
}
}
int main()
{
scanf("%d", &n );
for(int i =1 ; i <= n ; ++ i ) {
scanf("%d%d", &a[i] , &m[i] );
M *= a[i] ;//最小公倍數
}
China();
printf("%d", (ans%M+M) % M );
return 0;
}
八. 中國剩餘定理Pro
暫時隻給出代碼。。
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define N 100005
using namespace std;
ll n ;
ll exgcd( ll a , ll b , ll &x , ll &y ) {
if( !b ) {
x = 1 , y = 0 ;
return a ;
}
ll u = exgcd( b , a%b , y , x );
y -= (a/b)*x ;
return u ;
}
ll exCRT() {
ll a1 , m1 ;
n -- ;
bool flag = 0 ;
scanf("%lld%lld", &a1 , &m1 );
while( n -- ) {
ll a2 , m2 , dis ;
scanf("%lld%lld", &a2 , &m2 );
dis = m1-m2 ;
ll x , y , u , lcm ;
u = exgcd( a1 , a2 , x , y );
if( dis%u )
flag = 1 ;
x = dis/u*x%a2 ;
m1 -= a1*x ;
a1 = a1/u*a2 ;
m1 %= a1 ;
}
if( flag )
return -1 ;
else return (m1%a1+a1)%a1 ;
}
int main() {
while( scanf("%lld", &n ) != EOF )
printf("%lld\n", exCRT() );
}
友善以後複習，查漏補缺
練習題
1. 計算系數
2. 求n以内互質數的個數
3. gcd(數論)
4. 迷路
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)