首页 > 其他分享 >PAT_A1015 Reversible Primes

PAT_A1015 Reversible Primes

时间:2023-11-01 09:57:14浏览次数:41  
标签:prime PAT int reversible system Reversible A1015 Primes Yes

reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.

Now given any two positive integers N (<105) and D (1<D≤10), you are supposed to tell if N is a reversible prime with radix D.

Input Specification:

The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.

Output Specification:

For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.

Sample Input:

73 10
23 2
23 10
-2

Sample Output:

Yes
Yes
No
#include<bits/stdc++.h>
using namespace std;
const int N = 100000+5;
int p[N], prim[N], c, d[111], dl;
void findPrim(int n){
	for(int i = 2; i <= n; i++)
		if(p[i]==0){
			prim[c++]=i;
			for(int j = i+i; j <= n; j+=i)p[j]=1;
		}
}

int reverRadix(int n, int r){
	dl=0;
	while(n){
		d[dl++] = n%r;
		n /= r;
	}
	for(int i = 0; i < dl; i++)
		n = n*r + d[i];
	return n;
}

int main(){
	findPrim(N);
	p[1] = 1; //测试点1报错
	while(1){
		int n, d;
		scanf("%d", &n);
		if(n < 0) return 0;
		scanf("%d", &d);
		if(p[n]) printf("No\n");
		else if(p[reverRadix(n, d)]) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

总结
1、 #数学问题
测试点1报错,原因是1不是素数也不是合数,需要添加特判p[1] = 1;

标签:prime,PAT,int,reversible,system,Reversible,A1015,Primes,Yes
From: https://www.cnblogs.com/Afinis/p/17802361.html

相关文章

  • PAT 甲级【1015 Reversible Primes】
    考察素数判断考察进制转换importjava.io.IOException;importjava.io.InputStreamReader;importjava.io.StreamTokenizer;publicclassMain{@SuppressWarnings("uncheck")publicstaticvoidmain(String[]args)throwsIOException{StreamTok......
  • SP13015 CNTPRIME -Counting Primes
    \(CNTPRIME\)-\(Counting\)\(Primes\)题目描述给定初始序列\(A\),然后对原序列有以下操作:操作\(1\):0lrv将区间\([l,r]\)全赋值为\(v\)。操作\(2\):1lr查询区间\([l,r]\)注意:多组测试和特殊的输出。题目分析:就是一道板子题,首先我们先用欧拉筛筛出值域\([2,10^6]\)内的......
  • 洛谷题解 | AT_abc321_c Primes on Interval
    目录题目翻译题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2样例#3样例输入#3样例输出#3题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能......
  • Codeforces Round 884 (Div. 1 + Div. 2) B. Permutations & Primes
    给一个正整数\(n\),你需要构造一个\(n\)的排列\(p_1,p_2,\cdots,p_n\)。对于排列\(p\)的每个子段\([l,r]\),\(mex_{i=l}^{r}a_i\)的结果为质数的次数尽可能多。此处的\(mex\)最小排除值最低为\(1\)而非\(0\)。不难想到,小质数\(2,3\)容易构造。于是有......
  • 洛谷题解 | AT_abc321_c Primes on Interval
    目录题目翻译题目描述输入格式输出格式样例#1样例输入#1样例输出#1样例#2样例输入#2样例输出#2样例#3样例输入#3样例输出#3题目简化题目思路AC代码题目翻译【题目描述】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能......
  • SP13015 CNTPRIME -Counting Primes
    \(CNTPRIME\)-\(Counting\)\(Primes\)题目描述给定初始序列\(A\),然后对原序列有以下操作:操作\(1\):0lrv将区间\([l,r]\)全赋值为\(v\)。操作\(2\):1lr查询区间\([l,r]\)的质数个数。注意:多组测试和特殊的输出。题目分析:就是一道板子题,首先我们先用欧拉筛筛......
  • Primes on Interval(欧拉筛+二分+滑动窗口)
    【题面】你决定用素数定理来做一个调查.众所周知,素数又被称为质数,其含义就是除了数字一和本身之外不能被其他任何的数字除尽.现在给定一个正整数序列 ,+1,⋯ ,a,a+1,⋯,b (≤)(a≤b),请找出一个最小值 l,使其满足对于任意一个长度为 l 的子串,都包含 k 个质数.......
  • 时间可逆的马氏链(Time Reversible Markov Chain)
    逆向过程考虑一个具有转移概率\(P_{ij}\)和平稳概率\(\pi_i\)的已经达到平稳状态的遍历的(不可约+非周期+正常返)马尔科夫链。假设这个马氏链在平稳态的状态序列是\(\{X_m,X_{m+1},\cdots\}\),现在我们沿时间的反方向来看这条链,具体地,我们希望考察\(P(X_m=j|X_{m+1}=i,X_{......
  • Sum of Different Primes UVA - 1213
     选择K个质数,使它们的和等于N。问有多少种方案?例如,n=24,k=2时有3种方案:5+19=7+17=11+13=24 #include<iostream>#include<cstring>#include<cmath>#include<algorithm>usingnamespacestd;constintM=1e6+33;intb[M],c[M],tot;intn,m,f[2000][20];......
  • 题解 ARC111B【Reversible Cards】
    我们将值域中每个数视作一个节点,将每张卡片视作连接两个节点的边,则问题转化为:对于每条边都选择一个端点,使得被选择的节点总数最大。显然每个连通块可以分开处理。设连通块......