UVA 11889 Benefit
2024-09-25 20:59:49
题意: lcm(a, b) = c; c是a,b的最小共倍数, 现在给出a, c, 要你求出最小的b.
解题思路:
1. 如果c%a != 0 表示无解. 设b = c/a; 当gcd(a, b)==1时, 表示b就是要求的结果. 如果gcd(a, b) != 1;
那么lcm(a, b)一定小于c. 你想一想为什么会这样, 因为原本a中有一部份与结果b相同. 那么, 说明
a影响了b的值.
2. 例如: a = 12 = 2^2*3^1, b = 16 = 2^4, c = 48 = 2^4*3^1; b' = c/a = 4 = 2^2;
如果b'就是b与a不相同的部分. 那么我们求出的b‘ 如果gcd(a, b') != 1表明a有一部份影响了结果.
这样我们要求出原来的b, 就需要b'*gcd(a, b'), a/gcd(a, b');循环这个过程知道gcd(a, b') == 1为止.
那么b'得到原本的结果b.
//摘抄自http://blog.sina.com.cn/s/blog_77dc9e080101jhq7.html
ps:代码自己敲得。。。orz
#include <iostream>
using namespace std; int a,c,b;
int gcd (int a,int b){
return b==?a:gcd (b,a%b);
} int main (){
int t;
cin>>t;
while (t--){
cin>>a>>c;
if (c%a==){
b=c/a;
int d;
d=gcd(a,b);
while (d!=){
b*=d;
a/=d;
d=gcd (a,b);
}
cout<<b<<endl;
}
else
cout<<"NO SOLUTION"<<endl;
}
return ;
}
最新文章
- 常用function() 收集
- 《利用Python进行数据分析: Python for Data Analysis 》学习随笔
- 【C#】Json数据 排版算法
- Lingo语法
- python:页面布局 后台管理页面之常用布局
- vbaexcel
- iOS 获取当前城市
- flash图标插件
- Nginx - HTTP Configuration, the Location Block
- windows8 认识及使用
- ReactiveCocoa 谈谈RACMulticastConnection
- linux使用FIO测试磁盘的iops 【转载】
- angular.js 简单的表达式
- sts 去掉启动的rss功能
- Java语言导学笔记 Chapter 8 Thread
- YII 1.0 发表文章用到的小物件
- Python自动化--语言基础8--接口请求及封装
- 基于ROS的分布式机器人远程控制平台
- 【原创】ACR傻瓜式破解IC芯片卡
- Array 新增加的一些API用法