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;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容