数学总结

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
#define LL long long
LL n,M;
inline LL fd(){
    LL s=1,t=0;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)s=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){t=t*10+c-‘0‘;c=getchar();}
    return s*t;
}
inline LL qsm(LL x,LL y){
    LL base = 1;
    while(y){
        if(y&1) base = (1ll*base%M*x%M)%M;
        x = (x%M*x%M)%M;
        y>>=1;
    }
    return base;
}
int main()
{
    freopen("P3811.in","r",stdin);
    freopen("P3811.out","w",stdout);
    n = fd(),M = fd();
    for(re LL i=1;i<=n;++i)
        printf("%lld\n",(qsm(i,M-2)%M+M)%M);
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
#define LL long long
LL n,M,x1,y1,x2,y2;
inline LL fd(){
    LL s=1,t=0;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)s=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){t=t*10+c-‘0‘;c=getchar();}
    return s*t;
}
void exgcd(LL x,LL y){
    if(!y){
        x1 = 1;y1 = 0;
        return;
    }
    exgcd(y,x%y);
    x2 = x1,y2 = y1;
    x1 = y2;
    y1 = x2-x/y*y2;
}
int main()
{
    freopen("P3811.in","r",stdin);
    freopen("P3811.out","w",stdout);
    n = fd(),M = fd();
    for(re LL i=1;i<=n;++i){
        exgcd(i,M);
        printf("%lld\n",(x1%M+M)%M);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
#define LL int
const LL N = 3e6+5;
LL n,M,Inv[N];
inline LL fd(){
    LL s=1,t=0;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)s=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){t=t*10+c-‘0‘;c=getchar();}
    return s*t;
}
int main()
{
    freopen("P3811.in","r",stdin);
    freopen("P3811.out","w",stdout);
    n = fd(),M = fd();
    Inv[1] = 1;
    printf("%d\n",Inv[1]);
    for(re int i=2;i<=n;++i){
        Inv[i] = ((1ll*-Inv[M%i]*(M/i))%M+M)%M;
        printf("%d\n",Inv[i]);
    }
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
const int M = 1e7+5;
int n,m,lx,vis[M],Q[M];
inline int fd(){
    int s=1,t=0;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)s=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){t=t*10+c-‘0‘;c=getchar();}
    return s*t;
}
int main()
{
    n = fd(),m = fd();
    vis[1] = 1;
    for(re int i=2;i<=n;++i){
        if(!vis[i])
            Q[++lx] = i;
        for(re int j=1;j<=lx;++j){
            if(i*Q[j] > n)
                break;
            vis[i*Q[j]] = 1;
            if(i % Q[j] == 0)
                break;
        }
    }
    while(m--){
        int x = fd();
        if(vis[x]) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
const int M = 1e7+5;
int n,m,lx,vis[M],Q[M];
inline int fd(){
    int s=1,t=0;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)s=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){t=t*10+c-‘0‘;c=getchar();}
    return s*t;
}
int main()
{
    n = fd(),m = fd();
    vis[1] = 1;
    for(re int i=2;i<=n;++i){
        if(!vis[i])
            Q[++lx] = i;
        for(re int j=1;j<=lx;++j){
            if(i*Q[j] > n)
                break;
            vis[i*Q[j]] = 1;
            if(i % Q[j] == 0)
                break;
        }
    }
    while(m--){
        int x = fd();
        if(vis[x]) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define re register
int n;
inline int fd(){
    int s=1,t=0;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)s=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){t=t*10+c-‘0‘;c=getchar();}
    return s*t;
}
int phi(int x){
    int ans = x;
    for(re int i=2;i*i<=x;++i){
        if(x % i == 0){
            ans = ans - ans/i;
            while(x%i == 0)
                x /= i;
        }
    }
    if(x > 1) ans = ans - ans/x;
    return ans;
}
int main()
{
    freopen("kkk.in","r",stdin);
    freopen("kkk.out","w",stdout);
    n = fd();
    printf("%d",phi(n));
    return 0;
}