打卡信奥刷题（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考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

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

相关推荐

越过山丘，迎向开阔 | 百分点科技2026新年寄语

06、 Subagent 子代理完整指南：官方 Subagents、Task 委派与社区代理资源

Win11 搭建 Python 开发环境：Anaconda 安装、虚拟环境创建与 PyCharm 集成配置

更多资讯

关于电工证的文案真实经历告诉你怎么过实操考试

名山电工证在哪里报名多久拿证一个济源市政工人的真实经历

有四级电工证吗？保姆级教程教你快速拿证上岗

工地太忙根本没时间复习考试？电工证换本值不值得考？

嘉兴特种工报名网址值不值得考？建筑工人急需特种作业证上岗

土木多久能学会电工证吗 2026河南最新政策下怎么少走弯路

今日更新

西昌市电工作业查询怎么查？郑州报考避坑指南帮你少走弯路

西昌市电工作业查询通过率揭秘：怕考不过白交培训费？这几点要记牢

临夏电工证在哪里审官方报名入口怎么找

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？