數(shù)學(xué)問(wèn)題

1. 質(zhì)數(shù)篩

• 埃氏篩

利用當(dāng)前已經(jīng)找到的素?cái)?shù)，從后面的數(shù)中篩去當(dāng)前素?cái)?shù)的倍數(shù)，由預(yù)備知識(shí)一可知，當(dāng)前素?cái)?shù)已經(jīng)是篩去數(shù)的質(zhì)因子，如此下去能篩除所有之后的合數(shù)，是一種比較快的篩法

bool st[N]; //如果為true則被篩掉，不是質(zhì)數(shù)
int prime[N], cnt; //prime用于記錄質(zhì)數(shù)
void getprime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) //可以只篩出質(zhì)數(shù)的倍數(shù)即可
        {
            prime[cnt++] = i;
            for(int j = i + i; j <= n; j += i)
                st[j] = true;
        }
    }
}

• 線性篩

  和埃氏篩法的區(qū)別是對(duì)于每一個(gè)要篩除的數(shù)，歐拉篩法只篩除一次，而埃氏篩法會(huì)重復(fù)篩除，比如8和16同時(shí)被2和4篩去，推薦使用歐拉篩法，維護(hù)一個(gè)質(zhì)數(shù)表

  • 其中由于是從小到大枚舉質(zhì)數(shù)表，每個(gè)數(shù)一定被他的最小質(zhì)因子篩掉

bool st[N]; //如果為true則被篩掉，不是質(zhì)數(shù)
int prime[N], cnt; //prime用于記錄質(zhì)數(shù)
void getprime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

2.最大公約數(shù)與最小公倍數(shù)

利用輾轉(zhuǎn)相除法即歐幾里得算法遞歸求解，最大公約數(shù)則為兩數(shù)相乘后除最大公約數(shù)

int gcd(int a, int b)
{
    return b ? gcd(b, a % b), a;
}  

//或者
int gcd(int a, int b)
{
    if(b == 0) return a;
    else return gcd(b, a % b);
} 
//或者
__gcd(a,b)
    
//最大公約數(shù)為
a * b / __gcd(a,b)

3.同余模定理

如對(duì)取模

typedef long long ll;
ll mod(ll n)
{
    ll s = n
    for(int i = 1; i < 5; i++)
    {
        s = ((s % 3) * (n % 3));
    }
    return s % 3
}

還有便是對(duì)大數(shù)進(jìn)行取模，只能用字符串讀入，利用進(jìn)制轉(zhuǎn)換時(shí)的數(shù)位分解進(jìn)行求解

char s[1000];
int main()
{
    int n;//模n
    cin >> s;
    cin >> n;
    m = 0;
    for(int i = 0; i < strlen(s); i++)
        m = ((m * 10) % n + (s[i] - '0') % n) % n;
    //也可以加完后再取模，但會(huì)超出范圍
    cout << n;
    return 0;
}