2021.08.02(筛质数、分解质因数、快速幂）

1.1292. 哥德巴赫猜想 - AcWing题库

#include
#include
#include
#include
using namespace std;
const int maxn = 10000001;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];

void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int main(){
    int n;
    CalPhi();
    while(~scanf("%d",&n)){
        if(n==0){
            break;
        }
        int flag=0;
        for(int i=0;i){
            if(prime[i]%2==1&&vis[n-prime[i]]==0){
                printf("%d = %d + %d\n",n,prime[i],n-prime[i]);
                flag++;
                break;
            }
        }
        if(!flag){
            printf(" Goldbach's conjecture is wrong.\n");
        }
    }
}

注：注意标记质数的vis数组和prime数组两者的区别：

vis[i]=0/1：i是否是素数

prime[i]=j：第i个素数是j

2.1293. 夏洛克和他的女朋友 - AcWing题库

#include
#include
#include
#include
using namespace std;
const int maxn = 10000001;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];

void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int main(){
    int n;
    CalPhi();
    scanf("%d",&n);
    if(n==1){
        printf("1\n");
        printf("1\n");
    }else if(n==2){
        printf("1\n");
        printf("1 1\n");
    }else{
        printf("2\n");
        for(int i=2;i<=n+1;i++){
            if(vis[i]==0){
                printf("1 ");
            }else{
                printf("2 ");
            }
        }

    }
}

注：此题就是需要转换一下想法，主要是想明白只要是素数就输出1，只要是合数就输出2，即可

3.196. 质数距离 - AcWing题库

#include
#include
#include
#include
using namespace std;
#define int long long
const int maxn = 5e4+10;;
const int maxx=1e6+10;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];
int num[maxx]={0};
void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
int p[maxx]={0};
signed main(void){
    CalPhi();
    int a,b;
    while(~scanf("%lld %lld",&a,&b)){
        memset(num,0,sizeof num);
        memset(p,0,sizeof p);
        //利用质数表筛选出区间中的合数
        for(int i=0;i){
            if(prime[i]>=b){
                break;
            }
            for(int j=a/prime[i];j*prime[i]<=b;j++){
                if(j<2){
                    continue;
                }
                num[j*prime[i]-a]++;
            }
        }
        
        //通过合数的标记存入区间中的质数
        int minn=0,maxp=0;
        int flag=0;
        for(int j=0;j<=b-a;j++){
            if(num[j]==0&&j+a>1){
                p[flag++]=j+a;
            }
        }
        
        //找最大最小的问题
        for(int i=1;i+1){
            if(p[i+1]-p[i]>p[maxp+1]-p[maxp]) maxp=i;
            if(p[i+1]-p[i]1]-p[minn]) minn=i;
        }
        if(flag<2){
            printf("There are no adjacent primes.\n");
        }else{
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",p[minn],p[minn+1],p[maxp],p[maxp+1]);
        }

    }
}

注：一直tle的原因就是多组数读入的时候最好不要while(1)然后再进入循环体中进行读取，最好是通过while(~scanf("%d",&a))这样读入，不然第一种就会一直tle

4.1289. 序列的第k个数 - AcWing题库

#include
#include
#include
#include
using namespace std;
#define int long long
const int maxn = 1e6+10;;
const int maxx=1e6+10;
const int mod=200907 ;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];
void CalPhi() {
    vis[1] = 1, phi[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
        for (int j = 0; j < tot; ++j) {
            if (i * prime[j] > maxn) break;
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}
inline long long Pow(long long a, long long n, long long m) {
    long long t = 1;
    for (; n; n >>= 1, a = (a * a % m))
        if (n & 1) t = (t * a % m);
    return t % m;
}
signed main(void){
    int t;
    scanf("%lld",&t);
    while(t--){
        int a,b,c,k;
        scanf("%lld %lld %lld %lld",&a,&b,&c,&k);
        if(b*2==a+c){
            printf("%lld\n",(a+((k-1)*(b-a))%mod)%mod);
        }else{
            printf("%lld\n",(Pow(b/a,k-1,mod)*a)%mod);
        }
    }


}

注：简单的快速幂的使用

5.1290. 越狱 - AcWing题库

#include
#include
#include
#include
using namespace std;
#define int long long
const int maxn = 1e6+10;;
const int maxx=1e6+10;
const int mod= 100003 ;
bool vis[maxn]; // 0 为素数 1 为非素数
int tot, phi[maxn], prime[maxn];
inline long long Pow(long long a, long long n, long long m) {
    long long t = 1;
    for (; n; n >>= 1, a = (a * a % m))
        if (n & 1) t = (t * a % m);
    return t % m;
}
signed main(void){
    int n,m;
    scanf("%lld %lld",&m,&n);
    printf("%lld\n",(Pow(m,n,mod)%mod-m*Pow(m-1,n-1,mod)%mod+mod)%mod);


}

注：注意一下当mod的时候减法的时候需要在后面再加一个mod谨防负数(x%mod-y%mod+mod)%mod