博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【P1379】天才的约数和
阅读量:4841 次
发布时间:2019-06-11

本文共 1578 字,大约阅读时间需要 5 分钟。

来自GDOI2007,原题已不可考……

又自己做出来了好开心,找特殊性是个关键的切入点

原题:

这天周航遇到了靳泽旭。

   周航:“我是天才!”
   靳泽旭:“你为什么是天才?”
   周航:“你随便告诉我一个数字,我立即可以算出它所有约数之和,以及所有约数的倒数和!”
   靳泽旭:“换过来,我告诉你一个数的所有约数(包括1和该数本身)的和以及约数的倒数之和,你是天才你应该立即能推出这个数是什么!”
   周航被难倒了!
   现在,这个难倒了天才的题目就交到你手上了。

 

很像数论对吧

反正我没用数论知识

手玩小数据,玩到8的时候就可以发现一个很明显的规律:(不会搞表达式只能鼠绘一。一

把分母搞成一样的(通分)以后,分子就是所有约数和,分母是这个数,题目中也给出了约数和

分子上的约数和可能会和分母约掉,那么把分子和分母还原成约分之前的样子(分子分母同时*给出的约数和/分子)

如果给出的约数和%分子!=0,根据显然法可得,显然,无解

然后还需要验证一下,如果还原后的分母的约数和等于给出的约数和,还原后的分母就是答案

可以打表证明对于任意一组数据要么无解要么一组解,数学证明我不会(逃

在赛场上真不会也可以赌一下

然后搞一搞就行了,代码很好写

找特殊性是切入点,打表大法好

代码:

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std; 7 long long read(){
long long z=0,mark=1; char ch=getchar(); 8 while(ch<'0'||ch>'9'){
if(ch=='-')mark=-1; ch=getchar();} 9 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();}10 return z*mark;11 }12 long long a,b,c;13 long long jie(long long x){14 int _q=int(sqrt(x*1.0));15 long long bowl=0;16 for(int i=1;i<=_q;i++)if(!(x%i)) bowl+=i+x/i;17 if(_q*_q==x) bowl-=_q;18 return bowl;19 }20 int main(){
//freopen("ddd.in","r",stdin);21 for(;;){
//徐王大法好22 a=read(),b=read(),c=read();23 if(!a && !b && !c) break;24 if(a%b){ printf("0\n"); continue;}25 c*=a/b;26 if(a!=jie(c)) printf("0\n");27 else printf("1 %lld\n",c);28 }29 return 0;30 }
View Code

 

转载于:https://www.cnblogs.com/JSL2018/p/6051436.html

你可能感兴趣的文章
ICDM评选:数据挖掘十大经典算法
查看>>
巧用「打印」功能实现PDF单页提取
查看>>
【转】Mongo初体验
查看>>
Java中synchronized和同步方法
查看>>
C语言学习记录_2019.01.29
查看>>
个人简历
查看>>
7 Sentences You Shouldn't Say to Your Boss - EVER
查看>>
TurtleBot3-基础例程
查看>>
动态规划之矩阵链
查看>>
Chrome 中的 JavaScript 断点设置和调试技巧 (转载)
查看>>
在Linux shell脚本中root切换到普通用户执行脚本或命令的方法
查看>>
rem,em,px
查看>>
《TCP/IP 详解 卷1:协议》第 10 章:用户数据报协议
查看>>
前端学数据库之基础操作
查看>>
python模块pymysql
查看>>
DAY-9 Linux基础及常用命令(5)
查看>>
unittest-mock-from-import
查看>>
node入门学习(二)
查看>>
通过js禁止输入空格(试用场景:当用字符串拼接插入dom节点时,onkeyup这些方法都不好使可用这个)...
查看>>
Codeforces Edu Round 48 A-D
查看>>