B3828 [NICA #2] 优秀正整数

unknown_risk · 2023-08-21 21:32:38 · 题解

思路：本题只需要枚举 [\sqrt{L},\sqrt{R}] 的数即可，平方求各数位之和，再跑一下质数筛。由于 R\le 10^{12} 所以各数位之和一定小于等于 108。所以这题也是非常的水，朴素筛法埃筛和线性筛均可过此题。

My code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int l,r;
bool vis[110];
signed main()
{
    scanf("%lld%lld",&l,&r);
    vis[1]=vis[0]=1;
    for(int i=2;i<=110;i++)
    {
        for(int j=2;j*i<=110;j++)vis[i*j]=1;
    }
    int x=sqrt(l),y=sqrt(r),ans=1,flag=0;
    for(int i=x;i<=y;i++)
    {
        if(i*i<l)continue;
        int sum=0;
        int num=i*i;
        while(num)
        {
            sum+=(num%10);
            num/=10; 
        }
        if(!vis[sum])ans=((ans%mod)*(i*i%mod))%mod,flag=1;
    }
    if(!flag)puts("0");
    else printf("%lld",ans);
    return 0;
}