信息学奥赛一本通 2082:【21NOIP提高组】报数 | 洛谷 P7960 [NOIP2021] 报数
admin
2024-01-19 20:17:05
0

【题目链接】

ybt 2082:【21NOIP提高组】报数
洛谷 P7960 [NOIP2021] 报数

【题目考点】

1. 筛法求质数

2. 因数

3. 数字拆分

4. 链表思想

【解题思路】

根据新的规则,任何一个十进制中某一位含有7的数字的倍数都不能报出来。
那么不能报出来的数字一定存在某一位是7的因数。
该题核心点为:如何判断一个数字的所有因数中,存在因数某一位是7。简单说成:判断某数字的因数中是否包含7。

解法1:枚举(70分)

has7函数:使用数字拆分的方法判断一个数字中是否有一位为7(是否包含7)。
设函数fac7,fac7(n)返回值表示n的因数中是否包含7。

  • 先枚举出n的所有因数,可以枚举所有满足i≤ni\le \sqrt{n}i≤n​的i,如果n能整除i,那么i及n/i都是n的因数。
  • 用has7函数判断n的因数中是否包含7,如果存在包含的情况,那么fac7函数返回true。如果不存在包含7的情况,返回false。

主函数中,对于每次输入的x,

  • 如果x的因数中包含7,那么输出-1。
  • 否则从x+1开始,不断判断后面的每个数字的因数中是否包含7。如果找到某个数字的因数中不包含7,那么就输出这个数字。

has7的复杂度为O(logn)O(log n)O(logn),fact7的复杂度为O(n⋅logn)O(\sqrt{n}\cdot log n)O(n​⋅logn),询问次数T最大为10510^5105,输入的x最大为10710^7107。极端情况下,要对每个数字判断一下它的因数中是否有7,复杂度为O(nn⋅logn)O(n\sqrt{n}\cdot log n)O(nn​⋅logn),在n达到10710^7107时,总运算次数一定会超过10810^8108,会超时。
实际情况,用该方法写出代码提交,可以得70分。

解法2:筛法(100分)

该问题要做10510^5105次的询问,如果预先确定了每个可能的数字的的因数中是否包含7,那么每次询问的复杂度为O(1)O(1)O(1)。
类比判断多次询问的数字是不是质数的问题,可以通过筛法求质数表,而后询问的方法来减少复杂度。本题也可以采用类似的筛法。

设数组fac7,fac7[i]表示数字i的因数中是否包含7,数组所有元素初值都为false。
显然fac7[1]为false,i从2开始循环到10710^7107

  • 如果fac7[i]为true,则略过。
  • 如果fac7[i]为false,那么使用has7函数判断数字i中是否某一位是7。如果是,那么对所有满足i≤107i\le 10^7i≤107的i的倍数j,都把fac7[j]设为true。

对于输入的x,如果x的因数包含7,即fac7[x]为真,那么输出-1。
否则,要输出x的下一个因数包含7的数字。如果在这里枚举x后的每个数字看其因数是否包含7,则复杂度过高。
这里可以设一个链式结构,设数组nextNot7,nextNot7[i]表示数字i的下一个因数不包含7的数字。该数组的值可以在做筛法的过程中生成,具体见代码注释。
在生成该数组后,x的下一个因数不包含7的数字就是nextNot7[x]
【注意】输入的x可以是10710^7107,而10710^7107是一个因数不包含7的数字,它的下一个因数不包含7的数字是100000011000000110000001,因此在做筛法时,最后一次循环时i应该是10000001,使得nextNot7[10000000]为10000001才可以。

【题解代码】

解法1:枚举(70分)

#include 
using namespace std;
bool has7(int n)//判断数字n的某一位中是否有数字7 
{for(int a = n; a > 0; a /= 10)//n都是正整数,可以用for循环 if(a%10 == 7)return true;return false;
}
bool fac7(int n)//判断数字n是否有因数中包含7 
{for(int i = 1; i*i <= n; ++i)if(n%i == 0 && (has7(i) || has7(n/i)))return true;return false;	
}
int main()
{int t, x, r;scanf("%d", &t);while(t--){scanf("%d", &x);if(fac7(x))printf("-1\n");else{for(r = x+1; fac7(r); ++r);//如果r因数中有7,就看下一个数字。直到找到一个因数中没有7的数字。 printf("%d\n", r);}}return 0;
}

解法2:筛法(100分)

#include 
using namespace std;
#define N 10000000
bool fac7[N+2];//fac7[i]:数字i的因数中某一位是否包含7 
int nextNot7[N];//lastNot7[i]:数字i向后找第1个因数中不包含7的数字 
bool has7(int n)//判断数字n的某一位中是否有数字7 
{for(int a = n; a > 0; a /= 10)//n都是正整数,可以用for循环 if(a%10 == 7)return true;return false;
}
void screen()//普通筛法 
{int lastNot7 = 1;//上一个因数中不包含7的数字 for(int i = 2; i <= N+1; ++i){if(fac7[i] == false)//如果还没有判断i{if(has7(i))//如果i中某一位包含7 { for(int j = i; j <= N; j += i)//i的所有倍数的因数中都包含7 fac7[j] = true;}else//确定i的因数不包含7 {nextNot7[lastNot7] = i;//lastNot7的下一个不包含7的数字是i lastNot7 = i;//lastNot7变为i }}}
}
int main()
{int t, x, i;screen();//筛法得到fac7scanf("%d", &t);while(t--){scanf("%d", &x);if(fac7[x])printf("-1\n");elseprintf("%d\n", nextNot7[x]);}return 0; 
}

相关内容

热门资讯

梅花易数在风水中的运用 梅花易数在风水中的运用我给你举列子八卦 对应的就是 6亲与方位与吉凶这就是风水
求一些有意义的的广告词,随便哪... 求一些有意义的的广告词,随便哪方面都可以!有了神舟还需要联想吗?我觉得太平洋保险的很好:平日汇聚一滴...
读了七彩虾一文,你觉得可以为老... 读了七彩虾一文,你觉得可以为老年人做些什么事情呢?读了七彩虾一文,你觉得可以为老年人做些什么事情呢?...
一年级学了姓氏歌学到了什么 一年级学了姓氏歌学到了什么更加深入的了解了中国传统文化培养了热爱祖国的真挚情感,姓氏歌让我对中国很多...
EDG打破了四大记录,分别是哪... EDG打破了四大记录,分别是哪四大记录?EDG打破了四大记录,分别是:LPL首位S系列赛首位国产冠军...
男主北冥夜女主慕云瑾是什么小说 男主北冥夜女主慕云瑾是什么小说是《恶魔的点心:宝贝,来伺候!》 作者:凉小桃
戚薇嫁给李承铉婚后生活超幸福,... 戚薇嫁给李承铉婚后生活超幸福,你向往异国恋吗?我一点都不向往异国恋,我觉得两国的文化会有很大的不同,...
南瓜车是什么意思? 南瓜车是什么意思?卡片中文名:南瓜车 等级:3星 卡种:效果怪兽 属性:地属性 种族:植物族 特殊效...
金海心在美丽俏佳人里的那个内弯... 金海心在美丽俏佳人里的那个内弯的短发是什么发型?那个发型确实挺好看的......不过不知道叫什么- ...
我的朋友今年11岁,得了急性淋... 我的朋友今年11岁,得了急性淋巴细胞白血病,想咨询一下儿童急淋一般不需要做移植,单靠化疗就可以治愈,...
分手后女生发家乡红枣树是什么意... 分手后女生发家乡红枣树是什么意思啊祝你以后平安吉祥的意思。红枣树有很多层意思,既然分手了,女朋友发家...
寻求类似斗破的小说 寻求类似斗破的小说凡人修仙传 绝对给力斗医、焚尽八荒、禁血红莲、召唤万岁等等。。。。绝对好看。。...
网络上好看的书籍有哪些? 网络上好看的书籍有哪些?张小娴和亦舒的全部书籍...个人觉得很经典...尤其是张小娴的系列真的是太赞...
为什么说周不疑天生废才? 为什么说周不疑天生废才?三国三国 觉得对他的评价不够妥当周不疑是谁?小说家言,不足以考。
时间をかける 时间をかかる 有... 时间をかける 时间をかかる 有什么区别?请举例说明 顺便打出相应的汉字 谢谢楼主出错了。时间を挂ける...
小燕子为什么要飞回南方? 小燕子为什么要飞回南方?1、燕子是以昆虫为食的,且它们从来就习惯于在空中捕食飞虫,而不善于在树缝和地...
有关汽车 有关汽车在汽车的速度表上,没开之前有两个灯亮:一个是油壶表示什么意思。 还有就是像温度计一样的表是什...
怎么样能更好的经营一个小家庭? 怎么样能更好的经营一个小家庭?遇到事情换位思考!!!两个人爱情保鲜,都想着对方,买点小礼物什么的。当...
含有计数单位的四字成语 含有计数单位的四字成语含有计数单位的四字成语 一日千里yī rì qiān lǐ【解释】原形容马...
成语玩命猜,舟字被水冲走的成语 成语玩命猜,舟字被水冲走的成语顺其自然(顺其自然)shùn qí zì rán[释义] 顺:顺应。...