打卡信奥刷题（3445）用C++实现信奥题 P10404 「XSOI-R1」原神数

2026/7/14 7:46:12

P10404 「XSOI-R1」原神数

题目描述

原神数xxx需要同时满足以下条件：

xxx为质数。
xxx的十进制位两两不同。

比如131131131不是原神数，因为他的百位和个位相等；424242也不是，因为不是质数；171717就是一个原神数。

有qqq次询问，现在要你求出lll到rrr之间的原神数数量。

输入格式

第一行一个正整数qqq。

接下来qqq行每行两个正整数lll，rrr。

输出格式

qqq行qqq个正整数，表示答案。

输入输出样例 #1

输入 #1

4 45 66 100 140 2 90 114514 1919810

输出 #1

4 6 23 13321

说明/提示

【样例解释 #1】

在100∼140100 \sim 140100∼140之间的原神数有103,107,109,127,137,139103,107,109,127,137,139103,107,109,127,137,139，共666个。

数据规模与约定

本题采用捆绑测试。

subtask 0（15 pts）：1≤l≤r≤1021 \le l \le r \le 10^21≤l≤r≤102。
subtask 1（15 pts）：1≤l≤r≤1041 \le l \le r \le 10^41≤l≤r≤104。
subtask 2（35 pts）：1≤l≤r≤1071 \le l \le r \le 10^71≤l≤r≤107。
subtask 3（35 pts）：1≤l≤r≤10181 \le l \le r \le 10^{18}1≤l≤r≤1018。

对于所有数据，保证1≤l≤r≤10181 \leq l \leq r \leq 10^{18}1≤l≤r≤1018，1≤q≤1051 \leq q\leq 10^51≤q≤105。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+50;intpr[N],tot,q;longlongl,r;vector<int>Genshin;boola[N]={1,1},vis[10];voidzhi(){for(inti=2;i<=N;i++){if(!a[i])pr[++tot]=i;for(intj=1;j<=tot&&i*pr[j]<=N;j++){a[i*pr[j]]=1;if(i%pr[j]==0)break;}}}boolispr(intx){if(x<=N)return!a[x];for(inti=1;pr[i]*pr[i]<=x;i++)if(x%pr[i]==0)return0;return1;//没有就是质数}voiddfs(intlen,intstep,intgoal){if(len==goal){//达到目标长度if(ispr(step))Genshin.push_back(step);//判断是不是质数return;}for(inti=0;i<=9;i++){if(len==0&&i==0)continue;//特判第一位为零if(vis[i])continue;//保证没被使用过vis[i]=1;//标记dfs(len+1,step*10+i,goal);//继续递归vis[i]=0;//回溯}}signedmain(){scanf("%d",&q);zhi();for(inti=1;i<=9;i++)dfs(0,0,i);//生成数while(q--){scanf("%lld%lld",&l,&r);printf("%d\n",upper_bound(Genshin.begin(),Genshin.end(),r)-lower_bound(Genshin.begin(),Genshin.end(),l));}return0;}