从【BZOJ4173】谈做题技巧
2024-09-02 05:19:49
题目描述
-------------------------------------------------------------------------------------------------------------------------------------------
正常题解:
特别的做题技巧
我们一上来,先写一个打表程序,打出一系列n,m对应的答案。
我们发现,对于素数n,m 他们的答案总是(n-1)*n*(m-1)*m。
一开始,我们先稳了一个素数的情况,起码也得有20分吧!心态放好!
然后,我们来思考为什么素数有这样的性质:
如果你对欧拉函数有足够的了解的话,你会知道,对于一个素数P 他的欧拉函数是P-1
那么,刚才的M-1 N-1 实际上是欧拉函数,那么,对于和数是否也有这样的性质呢?
答案是显然的。
这就是计算机的优点,虽然无法给出正确证明,但是可以通过大量实验数据,得到一个令人信服的结论。
做题总耗时: 打表程序——2分钟,找规律——3分钟,写正解程序——5分钟。
一道难题就被我们10分钟干掉了。
信息学竞赛不应该是人类的拼命推理,推公式,而是人脑与计算机的完美结合。
附上正解代码
#include<iostream>
#include<cstdio>
#define N 40000
using namespace std;
const unsigned long long int mod = ;
int n,m;
unsigned long long phi(unsigned long long x)
{
unsigned long long int res = x,a = x;
for(unsigned long long int i=;i*i<=a;i++)
{
if(a%i==)
{
res = res/i*(i-);
while(a%i==)a/=i;
}
}
if(a>)res =res/a*(a-);
return res%mod;
}
unsigned long long a,b;
int main()
{
scanf("%llu%llu",&a,&b);
unsigned long long p1 = phi(a),p2=phi(b),ans=;
ans=p1%mod*p2%mod*(a%mod)%mod*(b%mod)%mod;
printf("%llu",ans);
}
最新文章
- selenium 页面截图并保存
- Ubuntu 14.04 编译安装 husky
- java.lang.IllegalStateException: The specified child already has a parent. You must call removeView() on the child&#39;s parent first.
- Python for Informatics 第11章 正则表达式二(译)
- java语法糖3 深入剖析Java中的装箱和拆箱
- git学习——<;一>;git安装
- 《Java编程那点事儿》读书笔记(四)——String和StringBuffer
- QQ互发消息
- Android(java)学习笔记123:Clock app编写报错01
- laravel4通过控制视图模板路劲来动态切换主题
- 虚拟机下opensips 启动
- httpd的简单配置(转)
- #pragma预处理命令
- 二叉排序树插入C语言版 递归步骤理解
- Spring框架(1)---Spring入门
- Android Studio2.0 教程从入门到精通Windows版 - 提高篇
- UITableViewCell 获取当前位置
- PAT A1126 Eulerian Path (25 分)——连通图,入度
- Linux中的邮件发送
- WebSocket教程(二)
热门文章
- 解决opacity属性在低版本IE浏览器下失效的方法
- 探究算子find_shape_model中参数MaxOverlap的准确意思
- 关于在线文本编辑器防XSS注入攻击问题
- WPF设置Window的数据上下文(DataContext)为自身
- qt QTcpServer与QTcpSocket通讯
- SFTP 安装与配置
- socket收发消息
- SSL握手通信详解及linux下c/c++ SSL Socket代码举例
- 好久没做.Net开发了,今天配置IIS和.Net Framework 4.0遇到点问题
- 在sublime text中添加JavaScript的build-system