青岛大学软件梦工厂蓝桥讲课_素数题解

Linnea ·

更新时间:2024-11-10

· 853 次阅读

A.zx学长与失落城

使用筛法将小于1e6的素数输出,注意格式输出即可.
下面是标程代码

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int N = 1e6+5;
int vis[N];
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (vis[i]) continue;
        for (int j = 2; j * i <= n; j++)
            vis[i*j] = 1;
    }
    bool flag = 1;
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (vis[i]) continue;      
        if (flag) flag = 0;
        else printf(" ");
        printf("%d", i);
        if (++cnt%5 == 0) {puts("");flag = 1;}
    }
}
int main()
{
    init(1e6);
    return 0;
}

B.zx学长与城池守卫

O(n2)O(n^2)O(n2)枚举所有组合,素数判断加简单模拟即可得出答案.先使用筛法将素数筛出,已便后续判断.
下面是标程代码

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int N = 1e6+5;
int vis[N], a[N];;
bool che(int x, int y)
{
    int g[10], cnt = 0;
    int n = a[x];
    while(n)
    {g[++cnt] = n%10; n /= 10;}
    n = a[y];
    while(n)
    {g[++cnt] = n%10; n /= 10;}
    int ans = 0;
    for (int i = cnt; i>=1; i--)
        ans = ans * 10 + g[i];
    if (vis[ans]) return 0;
    for (int i = 1; i <= cnt; i++)
        if (g[i] != g[cnt-i+1]) return 0;
    return 1;
}
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (vis[i]) continue;
        for (int j = 2; j * i <= n; j++)
            vis[i*j] = 1;
    }
}
int main()
{
    init(1e6);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && che(i, j)) ans++;
    printf("%d\n", ans);
    return 0;
}

C.zx学长与素数国王

先用筛法将素数筛出,然后对于prime数组进行二分查找两个端点l,r,即可得出三个答案.
下面是标程代码:

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int N = 1e6+10;
int vis[N], prime[N];
int cnt = 0;
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (vis[i])  continue;
        prime[++cnt] = i;
        for (int j = 2; j * i > m;
    while(m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = lower_bound(prime+1, prime+cnt+1, l) - prime;
        r = upper_bound(prime+1, prime+cnt+1, r) - prime;
        printf("%d %d %d\n", prime[l], prime[r-1], r- l);
    }
    return 0;
}

D.zx学长与游戏神特图

依据题意,我们要找每个数的最小非1因子,显然无论是欧拉筛还是埃氏筛,都可以完成这个任务,(因为欧拉筛会得出每个数的最小质因子,埃氏筛可以得出每个数的所有因子),标程使用埃氏筛.
下面是标程代码:

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define min(x, y) ((x)>(y)?(y):(x))
#define max(x, y) ((x)>(y)?(x):(y))
using namespace std;
const int N = 1e7+10;
const int inf = 0x3f3f3f3f;
int vis[N], prime[N];
int cnt = 0;
void init(int n)
{
    memset(vis, inf, sizeof(vis));
    for (int i = 2; i <= n; i++)
    {
        if (vis[i] != inf)  continue;
        vis[i] = i;
        for (int j = 2; j * i > n;
    bool flag = 1;
    while(n--)
    {
        int p;
        scanf("%d", &p);
        if (flag) flag = 0;
        else printf(" ");
        printf("%d", vis[p]);
    }
    return 0;
}

E.zx学长与王国保卫战

首先我们通过筛选,我们发现前2e4个数中有2e3左右的素数,提示我们使用O(n2)O(n^2)O(n2)预处理,然后可以O(logn)O(logn)O(logn)查询,具体做法是,如果我们定义dp[l][r]dp[l][r]dp[l][r]为区间[pl,pr][p_l,p_r][pl,pr](分别表示第l和第r个素数)中符合要求的数对的数量,那么我针对一个素数对(px,py)(p_x,p_y)(px,py)如果有px+py−1p_x+p_y-1px+py−1为素数,那么这个素数对,将会在dp[1→x][y→n]dp[1\rightarrow x][y\rightarrow n]dp[1→x][y→n]的范围内提供一个有效对.这时我们发现,其是一个以(1,py)(1,p_y)(1,py)为左上角(px,n)(p_x,n)(px,n)为右下角的矩形范围,所以针对每个符合要求的素数对,可以使用二维差分进行O(1)O(1)O(1)修改,然后然后进行二维前缀和的求取(O(n2)O(n^2)O(n2)),此时我们完成O(n2)O(n^2)O(n2)的预处理,得到dpdpdp二维数组,然后针对每次查询,我们都进行二分操作,查询在那两个素数范围内,输出相应的dpdpdp值即可(筛选素数时筛到4e4!,因为要判断p1+p2−1p_1+p_2-1p1+p2−1是否为素数).
下面是标程代码:

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define min(x, y) ((x)>(y)?(y):(x))
#define max(x, y) ((x)>(y)?(x):(y))
using namespace std;
const int N = 4e4+10;
const int M = 2300;
const int inf = 0x3f3f3f3f;
int vis[N], prime[N];
int dp[M+5][M+5];
int cnt = 0;
void init(int n)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i <= n; i++)
    {
        if (vis[i])  continue;
        prime[++cnt] = i;
        for (int j = 2; j * i <= n; j++)
            vis[i*j] = 1;
    }
}
void initdp()
{
    for (int i = 1; i = 2e4) break;
        for (int j = i+1; j = 2e4) break;
            int x = prime[i], y = prime[j];
            if (vis[x+y-1]) continue;
            dp[1][j]++;
            dp[i+1][j]--;
            dp[1][M+1]--;
            dp[i+1][M+1]++;
        }
    }
    for (int i = 1; i <= M; i++)
        for (int j = 1; j > t;
    while(t--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        if (l > r) swap(l, r);
        l = lower_bound(prime+1, prime+cnt+1, l) - prime;
        r = upper_bound(prime+1, prime+cnt+1, r) - prime - 1;
        printf("%d\n", dp[l][r]);
    }
    return 0;
}

F.zx学长与神庙传说

我们不妨定义数组dp[i]dp[i]dp[i],如果dp[i]==1dp[i]==1dp[i]==1我们就认定当数字是iii时,先报数的人将会取胜,否则如果dp[i]==0dp[i]==0dp[i]==0,则意味着,先报数的人会输掉,那么我们如果可以求出当前数nnn的dpdpdp值,即可得出zx学长可不可以赢,那么我们可以使用搜索,对于一个数iii来说,经过一次喊数后,它可以转移成i−pi-pi−p,其中ppp是所有小于iii的素数,那么在iii所有的可转移状态中如果有某个pkp_kpk它的dp[i−pk]==1dp[i-p_k]==1dp[i−pk]==1,就是说
转移到这个数字是先报数的必输,那么iii局面的先手,也就是先报数的人,将可以报数pkp_kpk,令局面进入先手必败态(下一回合的先手就是这个局面先手的敌人),所以iii局面是一个先手必胜态,即dp[i]==1dp[i]==1dp[i]==1,而试想一下,如果所有的可转移局面都没有一个值等于1,也就是说,对于iii状态的先手,他无论报什么数,都会进入先手必胜态,所以iii局面就是先手必败态,即dp[i]==0dp[i]==0dp[i]==0(有兴趣的同学可以了解一下博弈论的相关知识,了解一下一些简单经典博弈论模型,在省赛和国赛中均有可能遇到)
下面是标程代码:

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define min(x, y) ((x)>(y)?(y):(x))
#define max(x, y) ((x)>(y)?(x):(y))
using namespace std;
const int N = 1e4+10;
const int inf = 0x3f3f3f3f;
int vis[N], prime[N];
int dp[N];
int cnt = 0;
void init(int n)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i <= n; i++)
    {
        if (vis[i])  continue;
        prime[++cnt] = i;
        for (int j = 2; j * i <= n; j++)
            vis[i*j] = 1;
    }
}
int dfs(int n)
{
    if (dp[n] != -1) return dp[n];
    if (n == 0 || n == 1) return 0;
    for (int i = 1; i  n) break;
        if (!dfs(n-prime[i])) return dp[n] = 1;
    }
    return dp[n] = 0;
}
int main()
{
    init(1e4+5);
    memset(dp, -1, sizeof(dp));
    int t; cin >> t;
    while(t--)
    {
        int n; scanf("%d", &n);
        if (dfs(n)) puts("ohhhhhh!");
        else puts("Try again next time!");
    }
    return 0;
}

G.zx学长与魔镜

这个题是比较麻烦的题,但是比较容易理解,我们就寻找所有可能的相遇点,然后让zx学长的路线是最短路,国王的路线是最长路,即可找到在该相遇点下的最坏情况,然后比较所有可能的相遇点,取最大值,这个值就是最坏情况,然后和K比较即可.可能相遇点是,zx学长走到着的距离,大于等于国王的距离,而且,要注意的是应该是最短路径!!,且国王和zx学长能走的方向,zx学长和国王不可以一下一上,或者数一右一左的相遇,只能是一上一下,一左一右.
下面是标程代码:

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define min(x, y) ((x)>(y)?(y):(x))
#define max(x, y) ((x)>(y)?(x):(y))
using namespace std;
const int N = 1e5+10;
const int M = 1e3+5;
const int inf = 0x3f3f3f3f;
int vis[N], prime[N];
ll kdis[M][M];
ll zxdis[M][M];
ll  mp[M][M];
int cnt = 0;
void init(int n)
{
    prime[0] = inf;
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i <= n; i++)
    {
        if (vis[i])  continue;
        prime[++cnt] = i;
        for (int j = 2; j * i > n >> m >> K)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j = 1; i--)
            for (int j = m; j >= 1; j--)
                kdis[i][j] = max(kdis[i+1][j], kdis[i][j+1]) + abs(2 - mp[i][j]);
        memset(zxdis, inf, sizeof(zxdis));
        zxdis[1][0] = 0;
        ll ans = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j = kf)
                    ans = max(ans, min(zxdis[i-1][j], zxdis[i][j-1]) + kdis[i][j]);
                if (i != n && zxf == kf - 1)
                    ans = max(ans, kdis[i+1][j] + zxdis[i][j]);
                if (j != m && zxf == kf - 1)
                    ans = max(ans, kdis[i][j+1]+zxdis[i][j]);
            }
        if (ans <= K) puts("Win!");
        else puts("Wake up!");
    }
    return 0;
}

H.无题

统计所有n个数质因子种类的数量,我们进行试除,不过是用所有质数试除,然后我们每选择一个素数,就把场上所有这个因子除完,然后换下一个数,最终答案就是所有n个数质因子种类的数量.
下面是标程代码:

#include
#include
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define min(x, y) ((x)>(y)?(y):(x))
#define max(x, y) ((x)>(y)?(x):(y))
using namespace std;
const int N = 1e3+10;
const int inf = 0x3f3f3f3f;
int vis[N], prime[N];
int cnt = 0;
void init(int n)
{
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i <= n; i++)
    {
        if (vis[i])  continue;
        prime[++cnt] = i;
        for (int j = 2; j * i > n;
    for (int i = 1; i <= n; i++)
    {
        int te; scanf("%d", &te);
        for (int i = 1; i <= cnt; i++)
        {
            int tt = prime[i];
            if (te % tt) continue;
            v[tt] = 1;
            if (vis[te / tt] == 0) v[te / tt] = 1;
        }
        if (vis[te] == 0) v[te] = 1;
    }
    int cnt = 0;
    for (int i = 1; i <= 1e3+5; i++)
        if (v[i]) cnt++;
    printf("%d\n", cnt);
    return 0;
}

作者：KalznAsawind

大学素数软件

1024 个赞