题解：P16800 [蓝桥杯 2026 国 B] 方和质数

Evan2000 · 2026-06-11 13:29:10 · 题解

题意

找出 l 到 r 中第 k 个数位和为完全平方数且该数是质数的数。

思路

正常的暴力肯定不行，埃氏筛和线性筛数组开不了这么大，普通的判素数时间复杂度 O(\sqrt{x}) 太大会时间超限，分段筛我太蒟蒻不会，但是有一个好玩的东西：Miller–Rabin 素性测试！（来源于 OI Wiki）

有了这个东西，就不用怕时间超限了！其他的按题目模拟即可。

:::success[AC代码]

#include<bits/stdc++.h>
#define int __int128//快速幂的时候有可能会爆long long
using namespace std;
int jidi[]={0,2ll,325ll,9375ll,28178ll,450775ll,9780504ll,1795265022ll};
int ksm(int a,int b,int mod)
{
    int ret=1;
    while(b)
    {
        if(b%2==1)
        {
            ret*=a;
            ret%=mod;
        }
        a*=a;
        a%=mod;
        b/=2;
    }
    return ret;
}
bool judge(int x)//Miller–Rabin 素性测试!
{
    if(x<3 || x%2==0)
    {
        return x==2;
    }
    if(x%3==0)
    {
        return x==3;
    }
    int u=x-1;
    int t=0;
    while(u%2==0)
    {
        u/=2;
        t++;
    }
    for(int i=1;i<=7;i++)
    {
        int a=jidi[i]%x;
        int v=ksm(a,u,x);
        if(v==1 || a==0 || v==x-1)
        {
            continue;
        }
        int j;
        for(j=0;j<t;j++)
        {
            if(v==x-1)
            {
                break;
            }
            v=v*v%x;
        }
        if(j==t)
        {
            return false;
        }
    }
    return true;
}
int read()
{
    char ch=getchar();
    while(!isdigit(ch))
    {
        ch=getchar();
    }
    int ret=0;
    while(isdigit(ch))
    {
        ret=ret*10+(ch-'0');
        ch=getchar();
    }
    return ret;
}
void write(int x)
{
    if(x<10)
    {
        putchar(x+'0');
        return ;
    }
    write(x/10);
    putchar(x%10+'0');
}
signed main()
{
    int l=read(),r=read(),k=read();
    int tot=0;
    for(int i=l;i<=r;i++)
    {
        int j=i;
        int sum=0;
        while(j)
        {
            sum+=j%10;
            j/=10;
        }
        if((int)sqrt((long long)sum)*(int)sqrt((long long)sum)==sum && judge(i))
        {
            tot++;
        }
        if(tot==k)
        {
            write(i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}