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

P10404 「XSOI-R1」原神数题目描述原神数xxx需要同时满足以下条件xxx为质数。xxx的十进制位两两不同。比如131131131不是原神数因为他的百位和个位相等424242也不是因为不是质数171717就是一个原神数。有qqq次询问现在要你求出lll到rrr之间的原神数数量。输入格式第一行一个正整数qqq。接下来qqq行每行两个正整数lllrrr。输出格式qqq行qqq个正整数表示答案。输入输出样例 #1输入 #14 45 66 100 140 2 90 114514 1919810输出 #14 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 015 pts1≤l≤r≤1021 \le l \le r \le 10^21≤l≤r≤102。subtask 115 pts1≤l≤r≤1041 \le l \le r \le 10^41≤l≤r≤104。subtask 235 pts1≤l≤r≤1071 \le l \le r \le 10^71≤l≤r≤107。subtask 335 pts1≤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≤10181≤q≤1051 \leq q\leq 10^51≤q≤105。C实现#includebits/stdc.husingnamespacestd;constintN1e650;intpr[N],tot,q;longlongl,r;vectorintGenshin;boola[N]{1,1},vis[10];voidzhi(){for(inti2;iN;i){if(!a[i])pr[tot]i;for(intj1;jtoti*pr[j]N;j){a[i*pr[j]]1;if(i%pr[j]0)break;}}}boolispr(intx){if(xN)return!a[x];for(inti1;pr[i]*pr[i]x;i)if(x%pr[i]0)return0;return1;//没有就是质数}voiddfs(intlen,intstep,intgoal){if(lengoal){//达到目标长度if(ispr(step))Genshin.push_back(step);//判断是不是质数return;}for(inti0;i9;i){if(len0i0)continue;//特判第一位为零if(vis[i])continue;//保证没被使用过vis[i]1;//标记dfs(len1,step*10i,goal);//继续递归vis[i]0;//回溯}}signedmain(){scanf(%d,q);zhi();for(inti1;i9;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考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容