数论(GCD) HDOJ 4320 Arcane Numbers 1
2024-08-30 06:31:38
题意:有一个A进制的有限小数,问能否转换成B进制的有限小数
分析:0.123在A进制下表示成:1/A + 2/(A^2) + 3 / (A^3),转换成B进制就是不断的乘B直到为0,即(1/A + 2/(A^2) + 3 / (A^3)) * (B^m)。那么(B^m) 一定要能整除(A^n),转换一下就是A的质因子B都有,可以用GCD高效计算
收获:数论题做不来可以找找规律,想想会用什么知识求解
代码:
/************************************************
* Author :Running_Time!
* Created Time :2015-8-25 8:49:59
* File Name :A.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7; ll GCD(ll a, ll b) {
return b == 0 ? a : GCD (b, a % b);
} int main(){
int T, cas = 0; scanf ("%d", &T);
ll A, B, C;
while (T--) {
scanf ("%I64d%I64d", &A, &B);
while ((C = GCD (A, B)) != 1) A /= C;
printf ("Case #%d: %s\n", ++cas, A == 1 ? "YES" : "NO");
} return 0;
}
最新文章
- C main
- C#使用Expand、Shell32解压Cab、XSN文件
- 【POJ 1182 食物链】并查集
- jQuery(二)
- linux定时调度器每秒运行一次
- Best jQuery Plugins of the Month – May 2014
- 需求分析&;原型改进
- POJ1017 Packets---贪心
- 3D数学 矩阵常用知识点整理
- Three failed attempts of handling non-sequential data
- FPGA——入手(零)
- Perl的IO操作(2):更多文件句柄模式
- 6.方法_EJ
- vCenter server 的部署和实施
- Android 简历 怎么写? 月薪10K,20K+, 怎么拿到面试?
- ORM框架之SQLALchemy
- 【驱动】Flash设备驱动基础&#183;NOR&#183;NAND
- python import win32clipboard 报错DLL load failed: %1 不是有效的 Win32 应用程序。
- Python系列之入门篇——pytables及其客户端
- Jetty - Connector源码分析