自动搬运

查看原文

来自洛谷，原作者为

	unknown_risk 回忆是一种重逢，忘记是一种自由

搬运于2025-08-24 21:15:19，当前版本为作者最后更新于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;
}