hdu 1792 A New Change Problem(互质数之间最大不能组合数和不能组合数的个数)
题意:求互质的m和n的最大不能组合数和不能组合数的个数
思路:m和n的最大不能组合数为m*n-m-n,不能组合数的个数为(m-1)*(n-1)/2
推导:
先讨论最大不能组合数
因为gcd(m,n)=1,所以 0,n,2*n,3*n,...(m-1)*n(共m个数字)分别除以m,余数肯定不同,且为{0,1,2,3...m-1}中的某数
若存在非负数p,q使得pm+qn=x,x为可组合值,两边对m取余,则(q*n)%m==x%m,p*m>=0,所以只要x>q*n,x都能被组合出来。当q<m时,能出现所有余数,所以当x>=(m-1)*n时,x必定可被组合。
从(m-1)*n往下寻找,第二大的q*n为(m-2)*n=(m-1)*n-n,不妨令m<n。只要比(m-1)*n-n大且不与(m-1)*n同余的数字都符合要求,即(m-1)*n,(m-1)*n-1,...(m-1)*n-(m-1),都符合要求,只有(m-1)*n-m>(m-2)*n,且同余,在m>n的情况下,由于对于q*n相邻m-1个必定不同余,所以结果一样。
所以最大的不符合数是(m-1)*n-m,即m*n-n-m
再讨论不符合要求的方案数
从大到小讨论q*n(m>n)
①对于(m-1)*n,不符合要求的是比(m-1)*n小且与它同余的数,就是(m-1)*n-m,(m-1)*n-2*m...
②对于(m-2)*n,不符合要求的是(m-2)*n-m,(m-2)*n-2*m...
③对于n,不符合要求的就是,n-m..
所以ans=n/m+(2*n)/m+(3*n)/m...+((m-1)*n)/m=(m-1)*(n-1)/2
对于n*m/m=n,这个是整除的,所以(i*n+(m-i)*n)/m=n
由于i*n/m必定不整除,所以i*n%m+(m-i)*n%m=m;
因而(i*n)/m+((m-i)*n)/m=n-1,得出:ans=n/m+(2*n)/m+...((m-1)*n)/m=(n/m+(m-1)*n/m)+(2*n/m+(m-2)*n/m)+...=(n-1)*(m-1)/2
标准程序
#include<iostream>
using namespace std;
int main()
{
int m,n;
while(cin>>m>>n)
{
cout<<m*n-m-n<<" "<<(m-)*(n-)/<<endl;
}
return ;
}
最新文章
- Spring获取ApplicationContext
- fastJSON☞JSONParameters☞时区的修改☞时间最后有一个";Z";
- Hadoop_HDFS HA 及解决方案
- 笔记:修改centos的IP地址相关配置
- MyEclipse使用总结——使用MyEclipse打包带源码的jar包
- Android(java)学习笔记241:多媒体之 MediaPlayer使用
- 【递归】Vijos P1132 求二叉树的先序序列(NOIP2001普及组第三题)
- 通过原生js的ajax或jquery的ajax获取服务器的时间
- Socket 学习(三).3 TCP UDP 图解
- azkaben任务调度器
- HttpComponents 发送post get 请求
- Visual Studio Code-批量添加或删除注释行
- Python-递归初识-50
- vector、map 判断某元素是否存在、查找指定元素
- ARMV8 Procedure Call Standard
- 20165306 实验一Java开发环境的熟悉
- 从零开始学习Vue(四)
- Java面试题 corejava(一)
- 以OPC PowerTool 连接iFix与KEPWARE
- Mongodb3安装授权
热门文章
- IPC进程之间通信的几种方式
- Linux 系统管理命令 - free - 查看系统内存信息
- HO引擎近况20160710
- bzoj 1898: [Zjoi2005]Swamp 沼泽鳄鱼【dp+矩阵快速幂】
- 5 分钟掌握 JS 实用窍门技巧,帮你快速撸码--- 删除数组尾部元素、E6对象解构、async/await、 操作平铺嵌套多维数组等
- thunderbird 登录网易邮箱
- Ignatius and the Princess III HDU - 1028 || 整数拆分,母函数
- ";HIBERNATE_SEQUENCE"; does not exist问题处理
- Looper、MessageQueue、Message、Handler的关系
- ASP.NET MVC+Bootstrap个人博客之文章打赏(六)