Time Limit: 2 Seconds Memory Limit: 65536 KB
Singles' Day(or One's Day), an unofficial holiday in China, is a pop culture entertaining holiday on November 11 for young Chinese to celebrate their bachelor life. With the meaning of single or bachelor of number '1' and the huge population of young single man. This festival is very popular among young Chinese people. And many Young bachelors organize parties and Karaoke to meet new friends or to try their fortunes that day.
On Singles' Day, a supermarket has a promotional activity. Each customer will get a ticket on which there are two integers b and N, representing an integer M that only contains N digits 1 using b as the radix. And if the number M is a prime number, you will get a gift from the supermarket.
Since there are so many customers, the supermarket manager needs your help.
Input
There are multiple test cases. Each line has two integers b and N indicating the integer M, which might be very large. (2 <= b <= 16, 1 <= N <= 16)
Output
If the customer can get a gift, output "YES", otherwise "NO".
Sample Input
3 3 2 4 2 1 10 2
Sample Output
YES NO NO YES
Hint
For the first sample, b=3, N=3, so M=(111)3, which is 13 in decimal. And since 13 is a prime number, the customer can get a gift, you should output "YES" on a line.
题意:
给出 B,N(1 ~ 16),代表用 N 个 1 构成的 B 进制数。判断这个数是不是素数,是则输出 Yes,不是则输出 No。
思路:
N 进制化成十进制后判断是否素数即可。主要要开unsign long long,且循环到开方数,而不是数的一半,不然会超时。
一开始循环到num / 2 来判断,导致 TLE,后想了各种办法推了各种公式,也知道可以打表,但是一直以为是什么需要技巧的题目。
AC:
#include<stdio.h> int test(unsigned long long num) { if(num == 1) return 0; for(unsigned long long i = 2;i * i <= num;i++) if(!(num % i)) return 0; return 1; } int main() { int b,n; while(~scanf("%d%d",&b,&n)) { unsigned long long sum = 0,k = 1; for(int i = 0;i <= n - 1;i++) { sum += k; k *= b; } if(test(sum)) printf("YES\n"); else printf("NO\n"); } return 0; }
相关推荐
null必修3算法习题程序清单汇编 二分法 回文数判断 数字分离技术 十进制和其他进制转化 因数输出 质数判断 a+a.doc
java代码-使用java解决输出1000以内最大的n个质数及其和。输出形式“质数1+质数2+...+质数n=的源代码 ——学习参考资料:仅用于个人学习使用!
圆位置判定+质数判定+整根式化简三个功能,VB做得。。本人是新手,所以技术可能不太过关,偶尔会有出错的时候,希望高手帮忙优化下,谢谢!
C语言实现素数判断,输入一个数,判断是否为素数
质数判断程序-判断质数
我们需要写一个判断一个整数是否是一个素数的函数: 素数是什么呢? 是除了1和它本身以外没有任何的因子. 那么我们只要发现它的一个因子就可以说他不是素数,反之,返回true. 因子是什么? 一个数除以它的...
要求:1)以十进制输出这些素数,每行10 个,每输出一个素数都要有数秒的停顿;2)统计这些素数的个数,以十进制形式输出;3)计算这些素数之和,以十进制形式输出;4)数据的输入和结果的输出都要有必要的提示,且提示独占一行;5...
判断素数,可以修改初始值,使得判断素数的范围更大。
大数计算器及素数判断,c++带代码及word讲解,简短易懂!
题目:判断101-200之间有多少个素数,并输出所有素数。 1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙...
多种方法判断素数
用于判断一个数是否为素数,prim的C语言实现,自己写的,工参考。
简单的质数判断程序
Java学习~素数判断
结果如: modulus 13552351350449497466140191726480947600097303807021690643242001981410540990...
c#版的判断素数,可以在当前框输入数字,也可以在新建的窗口输入,再进行素数合数的判断
输入一个数,判断其是否是质数,提供了两种程序,值得深入研究
从键盘任意输入两个整数,输出两数之间的素数,素数判断用函数实现。 扩展要求:1)程序可以循环执行,判断完一组可以再进行下一组;可以设定一个特殊键退出 2) 当输入的两个数不是大于2,则重新输入 3)输入的数...
输入一个正整数m,判断其是否为素数,是的话输出YES,否则为NO
素数的判断,函数调用 素数分解成几个质因数相乘