筛质数

1292. 哥德巴赫猜想【线性筛】

https://www.acwing.com/problem/content/1294/
就先筛出所有的质数，然后枚举找即可。第一次找到的就是答案，因为俩数都是往中间靠的，故越先发现，差越大。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int prime[N],st[N],cnt,n;
void init()

    int len=1e6;
    for(int i=2;i<=len;i++)
    
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=len/i;j++)
        
            st[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        
    

int main(void)

    init();
    while(cin>>n,n)
    
        bool flag=0;
        for(int i=0;i<cnt;i++)
        
            if(!st[n-prime[i]])
            
                printf("%d = %d + %d\\n",n,prime[i],n-prime[i]);
                flag=1;
                break;
            
        
        if(!flag) puts("Goldbach's conjecture is wrong.");
    
    return 0;

1293. 夏洛克和他的女朋友【二分图】

https://www.acwing.com/problem/content/description/1295/
详细题解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n;
bool check(int x)

    for(int i=2;i<=x/i;i++) if(x%i==0) return true;
    return false;

int main(void)

    cin>>n;
    bool flag=0;
    for(int i=2;i<=n+1;i++) if(check(i)) a[i]=1,flag=1;
    if(flag) cout<<2<<endl;
    else cout<<1<<endl;
    for(int i=2;i<=n+1;i++)
    
        if(a[i]) cout<<2<<" ";
        else cout<<1<<" ";
    
    return 0;

196. 质数距离【大区间内筛质数】

https://www.acwing.com/problem/content/description/198/
详细题解

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long int LL;
int prime[N],cnt,st[N],l,r;
void init()

    cnt=0;
    memset(st,0,sizeof st);
    int n=1e6;
    for(int i=2;i<=n;i++)
    
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++)
        
            st[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        
    

int main(void)

    while(cin>>l>>r)
    
        init();
        memset(st,0,sizeof st);
        for(int i=0;i<cnt;i++)
        
            LL p=prime[i];
            for(LL j=max(2*p,(l+p-1)/p*p);j<=r;j+=p) st[j-l]=1;
        
        cnt=0;
        for(int i=0;i<=r-l;i++) if(!st[i]&&i+l>=2) prime[cnt++]=i+l;
        if(cnt<2) puts("There are no adjacent primes.");
        else
        
            int minv=1,maxv=1;
            for(int i=1;i<cnt;i++)
            
                int temp1=prime[i]-prime[i-1];
                int min_temp=prime[minv]-prime[minv-1];
                int max_temp=prime[maxv]-prime[maxv-1];
                if(temp1<min_temp) minv=i;
                if(temp1>max_temp) maxv=i;
            
            printf("%d,%d are closest, %d,%d are most distant.\\n",prime[minv-1],prime[minv],prime[maxv-1],prime[maxv]);
        
    
    return 0;

分解质因数

197. 阶乘分解

https://www.acwing.com/problem/content/199/
详细题解

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int prime[N],st[N],cnt;
void init(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[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        
    

int main(void)

    int n; cin>>n;
    init(n);
    for(int i=0;i<cnt;i++)
    
        int temp=0;
        for(int j=n/prime[i];j;j/=prime[i]) temp+=j;
        cout<<prime[i]<<" "<<temp<<endl;
    
    return 0;

快速幂

1289. 序列的第k个数【简单快速幂】

https://www.acwing.com/problem/content/1291/

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int mod=200907;
LL quick_mi(LL a,LL b,LL p)

    LL sum=1;
    while(b)
    
        if(b&1) sum=sum*a%p;
        b>>=1;
        a=a*a%p;
    
    return sum%p;

LL t,a,b,c,k;
int main(void)

    cin>>t;
    while(t--)
    
        cin>>a>>b>>c>>k;
        if(a+c==2*b) cout<<(a+(b-a)*(k-1))%mod<<endl;
        else cout<<a*quick_mi(b/a,k-1,mod)%mod<<endl;
    
    return 0;

1290. 越狱【组合数 / 快速幂】

https://www.acwing.com/problem/content/description/1292/
详细题解

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int mod=100003;
LL n,m;
LL quick_mi(LL a,LL b)

    LL sum=1;
    while(b)
    
        if(b&1) sum=sum*a%mod;
        b>>=1;
        a=a*a%mod;
    
    return sum%mod;

int main(void)

    cin>>m>>n;
    cout<<(quick_mi(m,n)-m*quick_mi(m-1,n-1)%mod+mod)%mod;
    return 0;