打卡信奥刷题（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 集成配置

更多资讯

大模型与NLP技术演进：从Transformer到实践应用

AI辅助教材编写：技术原理与实践指南

STM32+VS Code开发环境实战：GCC工具链配置与调试闭环

ESP32双模Wi-Fi+BLE真实坑点与工程避坑指南

2026示波器选型指南：从入门到车规级的全档位决策逻辑

Cilium ClusterMesh `inspect-policy-default-local-cluster` 命令详解：切换策略默认集群前的安全影响排查

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

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