数学基础

数学基础

1.快速幂

注意结果可能为负（c++出锅）最后答案（ans+mod）%mod

inline ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }   
    return (ans+MOD)%MOD;
}

2.快速乘

解决乘法爆long long 的问

正确的快速乘——from i207m

il ull qmul(const ull a,const ull b,const ull md)
{
    LL c=(LL)a*b-(LL)((ull)((long double)a*b/md)*md);
    return c<0?md+c:((ull)c>md?c-md:c);
}

3.最大公约数GCD

欧几里得算法正确性证明：

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

普通的辗转相除法求gcd需要用到取模，所以比较慢 ；

复杂度证明：当成O(log)

(b,a%b)
a%b<=min(b,a%b)/2
a>=b时每次至少缩减一半
a<b时下次a>b
所以复杂度最多2log(max(a,b))

证明:a%b<=min(a,a%b)/2
a>b时 b<=a/2 那么a%b<b<=b<=a/2
a>b时 b>a/2 那么a%b=a-b<=a/2
a<b时 a%b=a
证毕

用斐波那契数列的相邻两个数可以达到最坏复杂度

二进制gcd

可通过不断去除因子2来降低常数；

注意一些写法 0==(x&1) 必须这么写。。。亲手试过简写不可

inline int gcd(int x,int y){
    int i,j;
    if(x==0) return y; 
    if(y==0) return x; 
    for(int i=0;0==(x&1);i++) x>>=1;
    for(int i=0;0==(y&1);i++) y>>=1;
    if(j<i) i=j;
    while(1){
        if(x<y) x^=y,y^=x,x^=y;
        if(0==(x-=y)) return y<<i;//x=y时结束 
        while(0==(x&1)) x>>=1;        
    }
}

高精度gcd

但是由于高精度，难以用除法和取模，如果用二分乘法逼近复杂度爆炸

这里用的更相减损术，原复杂度(O(n))，必须优化到(O(logn))

①gcd(a,b)=gcd(b,a-b)

②gcd(2a,2b)=2gcd(a,b)

③gcd(2a,b)=gcd(a,b) (b是奇数)

优化：

对于(gcd(a,b)),如果(a,b)都是偶数，那么其gcd必然有因数2，则可以让a/=2,b/=2,最后ans*=2；

如果有一个偶数，那么其gcd 必然没有因数2，则可以直接让偶数/=2；

如果a,b都不是偶数，直接用更相减损术，(gcd(a,b)=gcd(b,a-b))

考虑一个数除二的最大次数是(logn)的。所以优化后更损相减部分的复杂度是(O(logn))的。

但需要注意的是，一般题目用辗转相除法复杂度是更优的。（取模计算量可以忽略的情况下）

piao来的代码。。。菜炸了不会高精

#include <iostream>
#include <cstring>
#include <cstdio>
#define N 10001
#define MB 10000
#define MLEN 4
using namespace std;
int ten[6]={1,10,100,1000,10000,100000};
typedef struct BI_t
{
    int x[N],len;
    BI_t operator - (const BI_t &t)
    {
        BI_t c;
        int l=max(len,t.len);
        memset(&c,0,sizeof(c));
        for(int i=1;i<=l;i++)c.x[i]=x[i]-t.x[i];
        for(int i=1;i<=l;i++)if(c.x[i]<0)c.x[i+1]--,c.x[i]+=MB;
        for(int i=l;i>=1;i--)if(c.x[i]){c.len=i;break;}
        return c;
    }
    void input()
    {
        memset(&x,0,sizeof(x));
        int slen;
        char str[N];
        scanf("%s",str);
        slen=strlen(str);
        for(int i=0;i<slen;i++)x[i/MLEN+1]+=(str[slen-i-1]-'0')*ten[i%MLEN];
        len=(slen-1)/MLEN+1;
    }
    void out()
    {
        printf("%d",x[len]);
        for(int i=len-1;i>=1;i--)printf("%04d",x[i]);
    }
    /*%04d 表示:在输出整数x的时候 按照4个位子的知空间左对齐 多余的位子用0代替
    例如:x=3 --> 输出:0003 x=33 --> 输出:0033)
    这里x=7 就是道0007
    %4.4 表示:输出的数的格式为:整数部分专为4位 小数部分为4位(多余的位子用0代替)
    (例如:3.24 --> 输出:0003.2400)*/
    bool operator < (const BI_t t)const
    {
        if(len!=t.len)return len<t.len;
        for(int i=len;i>=1;i--)
            if(x[i]!=t.x[i])
                return x[i]<t.x[i];
        return 0;
    }
}BI;

void div2(BI &a)
{
    if(a.x[a.len]==1)a.x[a.len]=0,a.x[a.len-1]+=MB,a.len--;
    for(int i=a.len;i>=1;i--)
    {
        a.x[i-1]+=(a.x[i]&1)*MB;
        a.x[i]/=2;
    }
}
void mul2(BI &a)
{
    for(int i=1;i<=a.len;i++)a.x[i]*=2;
    for(int i=1;i<=a.len;i++)if(a.x[i]>=MB)a.x[i+1]++,a.x[i]%=MB;
    if(a.x[a.len+1])a.len++;
}

BI gcd(BI a,BI b)//优化的更相减损术 
{
    int t=0;
    bool d1,d2;
    if(a<b)swap(a,b);
    while(b.len>1||b.x[1]!=0)
    {
        d1=!(a.x[1]&1);
        d2=!(b.x[1]&1);
        if(d1&&d2)div2(a),div2(b),t++;//如果都是偶数，除以二 
        else if(d1&&!d2)div2(a);
        else if(!d1&&d2)div2(b);
        else a=a-b;
        if(a<b)swap(a,b);
    }
    while(t)mul2(a),t--;
    return a;
}

int main()
{
    BI a,b;
    a.input(),b.input();
    gcd(a,b).out();
    return 0;
}

最小公倍数LCM

先除后乘防溢出

lcm(x,y) = x / gcd(x, y)* y;

(a*b=lcm(a,b)*gcd(a,b);)

lgP1372：

Description

从1~n中取(k)个数，求这(k)个数的最大公约数 的最大值

(1<=k<=n<=10^9)

Solution

因为两个数成倍数关系时，它们的最大公因数是两数中的较小数，也就是相对来说最大公因数较大

返回题目，这k个数其实就是：(x_1,x_2......x_k)，及x的1~k倍，但必须保证xk小于(n)，在上述条件下，能知道，符合条件的最大的x就是答案，为了找出最大的x，必须使(x_k)尽量接近(n)，因为c++的整数除法有自动取整的功能，所以所有情况下，n/k都是最终答案

例2

Description

已知正整数(a_0,a_1,b_0,b_1)，设未知正整数 (x) 满足：

1． (x) 和(a_0)的最大公约数是 (a_1)

2． (x) 和(b_0)的最小公倍数是 (b_1)。

求解满足条件的 (x) 的个数

Solution

详细证明戳这里

x是 (a1)的整数倍且是 (b1) 的因子

(sqrt b1) 枚举 (b1) 的因子，如果这个数是 a1 的整数倍，并且满足那两个式子，ans++

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int n,ans;
int a,a1,b,b1,x;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main()
{
    scanf("%d",&n);
     while(n--){
         scanf("%d%d%d%d",&a,&a1,&b,&b1);
         ans=0;
         if(b1%b!=0) {puts("0");return 0;}
         for(int i=1;i*i<b;i++){
             if(b%i==0){
                 x=b1/b*i;
                 if(gcd(x,b)==i&&gcd(x,a)==a1) ans++;
                 x=b1/b*(b/i);
                 if(gcd(x,b)==b/i&&gcd(x,a)==a1) ans++;
             }
        }
        int k=(int)sqrt(b);
        if(k*k==b&&b%k==0){
            x=b1/b*k;
            if(gcd(x,b)==k&&gcd(x,a)==a1) ans++;
        }
        printf("%d
",ans);
    } 
    return 0;
}

例3

Description

给定整数N，求1<=x,y<=N且(Gcd(x,y))为素数的
数对((x,y))有多少对.

4.算术基本定理（整数唯一分解定理）

约数集合的暴力方法 (O(sqrt n))——枚举到(sqrt n)

求1到n里面约数最多的数的 约数个数

Solution

　　根据约数和定理:对于一个大于1正整数(n)可以分解质因数：(n=p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*…*pk^a_k)则由约数个数定理可知n的正约数有((a_1+1)(a_2+1)(a_3+1)…(a_k+1))个，

　　暴力算出每一个数的约数的个数，超时！

　　根据唯一分解定理，我们知道每一个数都可以用质因子的积表示，而约数的个数只与指数有关！

　　我们知道pn>...>p3>p2>p1，那么假设我们存在某一个ak>a1 那么我们交换pkz与p1的指数，显然约数个数不变，但是数变小了！！！

　　也就是说对于任何n,m如果pn>pm那么an<am 要好一些，是不是最优的，不确定！但是在已经为我们淘汰了许多了。

　　我们枚举每一个质因子的质数，保证其指数递减。

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long
int prime[20] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};
ll n,ans;
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}
void dfs(int pos,ll num,ll sum,int zs){//第几个素数，约数个数，数大小，当前最大指数
    if(sum>n) return;
    ans=max(ans,num);
    for(int i=1;i<=zs;i++){
        ll res=qpow(prime[pos],i);
        if(sum>n/res) break;//注意不要用sum*res>n，炸long long
        dfs(pos+1,num*(i+1),sum*res,i);
    }
}
int main(){
    scanf("%lld",&n);
    dfs(1,1,1,30);
    printf("%lld
",ans);
}

反素数

Description

求1到n里面约数最多的数

Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int s[100];
ll num,sum,n;
int p[20]={1,2,3,5,7,11,13,17,19,22,23,29,31};
void dfs(ll yue,ll he,int x){//x是当前枚举到第几个素数
    if(x>12)return;
    if(yue>num || yue==num&&he<sum){
        num=yue;sum=he;
    }
    s[x]=0;
    while(he*p[x]<=n&&s[x]<s[x-1]){//保证指数递减
        s[x]++;
        dfs(yue*(s[x]+1),he*=p[x],x+1);
    }
}
int main(){
    while(scanf("%lld",&n)==1){
        s[0]=10000;
        dfs(1,1,1);
        printf("%lld
",sum);
        memset(s,0,sizeof(s));
        sum=0;num=0;
    }
    return 0;
}

例3：a^b的正约数之和 sumdiv poj1845

[先将a分解 a={p_1}^{r_1}*{p_2}^{r_2}*...*{p_k}^{r_k}\ a^b={p_1}^{r_1*b}*{p_2}^{r_2*b}*...*{p_k}^{r_k*b}\ 设r[i]*b=c[i]\ ans=prodlimits_{i=1}^ksumlimits_{j=0}^{c_i}p_i^j\ sumlimits_{j=0}^{c_i}p_i^j=(p_i^{c_i}-1)/(p_i-1) ~~~等比数列求和公式\ 法二直接用二分递归求：举例来说，1+a+a^2+a^3+a^4=(1+a)*(1+a^2)+a^2;\(1+a)=1*(1+a)。根据奇偶二分下去。只要只有一个数为止。\ 分数形式的取模也有两种方法： \ 1.逆元：(A/B)\%mod=A*B^{mod-2};\ 2.变换模值：(A/B)\%mod=(A\%(mod*B))/B\%mod\ ]

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod=9901;
LL mul(LL a,LL b,LL n)
{
    LL s=0;
    while(b)
    {
        if(b&1)
            s=(s+a)%n;
        a=(a*2)%n;
        b=b>>1;
    }
    return s;
}
LL qpow(LL a,LL b,LL n)
{
    a=a%n;
    LL s=1;
    while(b)
    {
        if(b&1)
        {
            s=mul(s,a,n);
        }
        a=mul(a,a,n);
        b=b>>1;
    }
    return s;
}
int main()
{
    LL a,b;
    while(cin>>a>>b)
    {
        if(a<=1||b==0){cout<<1<<endl;continue;}
        LL ans=1,i,j,k,t,n,m;
        n=(LL)sqrt(a+0.5);
        for(i=2;i<=n;i++)
        {
            if(a%i==0)
            {
                t=0;
                while(a%i==0){
                    a=a/i;
                    t++;
                }
                if((i-1)%mod==0)ans=ans*(qpow(i,t*b+1,mod*(i-1))/(i-1))%mod;
                else ans=ans*(qpow(i,t*b+1,mod)-1)*qpow(i-1,mod-2,mod)%mod;
            }
        }
        if(a>1)
        {
            if((a-1)%mod==0)ans=ans*(qpow(a,b+1,mod*(a-1))/(a-1))%mod;
            else ans=ans*(qpow(a,b+1,mod)-1)*qpow(a-1,mod-2,mod)%mod;
        }
        cout<<(ans+mod)%mod<<endl;
    }
    return 0;
}

#include<iostream>
using namespace std;
#define LL long long
const int mod=9901;
LL qpow(LL a,LL b,int mod){     
    LL ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return (ans+mod)%mod;
}
LL sum(LL a,LL b,LL mod){             //二分求等比数列前N项和
    if(b==0)
        return 1;
    if(b%2==1)
        return (sum(a,b/2,mod)*(qpow(a,b/2+1,mod)+1))%mod;
    else
        return (sum(a,b-1,mod)+qpow(a,b,mod))%mod;
}
int main(){
    LL a,b;
    LL ans;
    while(cin>>a>>b){
        ans=1;
        for(LL i=2;i*i<=a;i++){//将a分解，然后每个约数再^b
            if(a%i==0){
                LL s=0;
                while(a%i==0){
                    s++;
                    a/=i;
                }
                ans=ans*sum(i%9901,b*s,9901)%9901;
            }
        }
        if(a>=2) ans=ans*sum(a%9901,b,9901)%9901;
        cout<<ans<<endl;
    }
    return 0;
}

例4：正约数之和为n的数的个数

#include <bits/stdc++.h>
#define N 100000
#define LL long long
using namespace std;
LL q;
int a[(N+5)<<2],cnt=0,tot=0,pr[N+5];
bool vis[N+5];

void init(){
    for(int i=2;i<=N;i++){
        if(!vis[i]) pr[++tot]=i;
        for(int j=1;j<=tot && i*pr[j]<=N;j++){
            vis[i*pr[j]]=1;
            if(i%pr[j]==0)break;
        }
    }
}

inline bool ispr(int x){
    if(x==1)return 0;
    if(x<=N) return !vis[x];//素数表已筛过
    for(int i=1;pr[i]*pr[i]<=x;i++)
        if(x%pr[i]==0) return 0;
    return 1; //素数
}

//   目标约数和m，当前质数，ans
void dfs(LL now,int x,LL y){
    if(now==1){
        a[++cnt]=y;
        return;
    }
    if(now-1>=pr[x]&&ispr(now-1))
        a[++cnt]=y*(now-1);
    int i;
    LL p,tmp;
    for(i=x;pr[i]*pr[i]<=now;i++){
        tmp=pr[i];//枚举几次方
        p=pr[i]+1;//几次方+1
        for(;p<=now;tmp*=pr[i],p+=tmp){
            if(now%p==0) dfs(now/p,i+1,y*tmp);
        }
    }
    return;
}

int main(){
    init();
    int m,i;
    while(~scanf("%d",&m)){
        q=sqrt(m);
        memset(a,0,sizeof(a));
        cnt=0;
        dfs(1LL*m,1,1LL);
        printf("%d
",cnt);
        //if(cnt==0)return 0;
        sort(a+1,a+1+cnt);
        for(i=1;i<cnt;i++)
            printf("%d ",a[i]);
        if(cnt) printf("%d
",a[cnt]);
    }
    return 0;
}

例5：樱花

[设n!=z，y=z+d\ frac{1}{x}+frac{1}{z+d}=frac{1}{z}\ frac{x+z+d}{x*z+x*d}=frac{1}{z}\ z*(x+z+d)=x*z+x*d\ z^2+d*z=d*x\ x=frac{z^2}{d}+z,发现就是求(n!)^2的约数个数 ]

对于n!约数的个数

有公式： [n/p] + [n/p^2] + …. + [n/p^k] ——代码中的calc函数

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=1e12;
const int M=1e6;
const int mod=1e9+7;
int n,ans=1ll,r[M],cnt;
int prime[M],mindiv[M];
void init(int n){
    mindiv[0]=mindiv[1]=1;
    for(int i=2;i<=n;i++){
        if(!mindiv[i]) mindiv[i]=prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
            mindiv[i*prime[j]]=prime[j];
            if(i%prime[j]==0)break;
        }
    }
}
int calc(int n,int p){
    int sum=0;
    while(n) sum+=n/p,n/=p;
    return sum;
}
signed main(){
    scanf("%lld",&n);
    init(n);
    int ans=1;
    for(int i=1;i<=prime[0];i++)
        ans=(ans*(calc(n,prime[i])*2+1))%mod;//平方所以*2
    printf("%lld
",ans);
    return 0;
}