2254: 迷信的病人

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

医院为了方便对患者进行建档和管理，引入了9位整数ID号来标识每个病人。最近医院入住了一个迷信的病人，他认为ID号的好坏直接决定了自己的命运。他对ID号x有如下要求:
（1）x的前三位数构成的整数是素数
（2）x的后三位数构成的整数是平方数（所谓平方数，是指它是某一个正整数的平方，e.g. 1,4,9,16...）
（3）x中不包含"13"
为了避免不必要的医患矛盾，医院须尽量满足他的需求。现给定正整数区间[m,n]，请你判断存在几个满足病人需求的ID号。

输入

两个正整数m，n，以空格隔开。(999999999>=n>=m>=111111111)

输出

一个整数（满足要求的ID的个数）。

样例输入 复制 

157689476 157689687

样例输出 复制 

5

提示

存在5个满足要求的ID：157689484,157689529,157689576,157689625,157689676 

#include<bits/stdc++.h>
using namespace std;

int is_prime(int x) {
	if (x==0||x==1)
	    return 0;
	for (int i=2;i*i<=x;i++) {
		if (x%i==0)
		    return 0;
	}
	return 1;
}

int is_square(int x) {
	return sqrt(x)==(int)sqrt(x);
}

int is_include(int x,int y) {
	while (x>0) {
		int t=x%100;
		if (t==y)
		    return 1;
		x/=10;
	}
	return 0;
}

int main(){
    int m,n,ans=0;
    cin>>m>>n;
    for (int i=m;i<=n;i++) {
    	int a=i/1000000;
    	int b=i%1000;
    	if (is_prime(a)&&is_square(b)&&!is_include(i,13)) {
    		ans++;
		}
	}
    cout<<ans;
	return 0;
}

来源/分类

提交提交记录统计露一手!