正文 

当前位置： 首页 > java > java教程

bzoj1876:[sdoi2009]supergcd

YouSiki YouSiki     2022-08-14     265

关键词：

1876: [SDOI2009]SuperGCD

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 2999  Solved: 1011
[Submit][Status][Discuss]

Description

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约 数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比 赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。

Input

共两行： 第一行：一个数A。 第二行：一个数B。

Output

一行，表示A和B的最大公约数。

Sample Input

12
54

Sample Output

6

HINT

对于20%的数据，0 < A , B ≤ 10 ^ 18。
对于100%的数据，0 < A , B ≤ 10 ^ 10000。

Source

Day1

[Submit][Status][Discuss]

 

分析

高精度GCD

 

代码

 1 def math_gcd(a, b) :
 2     while b != 0 :
 3         t = a
 4         a = b
 5         b = t % a
 6     return a
 7 
 8 
 9 def main() :
10     number_a = int(raw_input())
11     number_b = int(raw_input())
12     print math_gcd(number_a, number_b)
13 
14 
15 if __name__ == "__main__" : main()
BZOJ_1876.py

 

@Author: YouSiki

bzoj1876:[sdoi2009]supergcd

1876:[SDOI2009]SuperGCDDescriptionShengbill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约数）！因此他经常和别人比赛计算GCD。有一天Shengbill很嚣张地找到了你，并要求和你比赛，但是输给Shengbill岂不是很丢脸... 查看详情

bzoj千题计划288：bzoj1876:[sdoi2009]supergcd(代码片段)

http://www.lydsy.com/JudgeOnline/problem.php?id=1876 高精压位GCD 对于  GCD(a,b) a>b 若 a 为奇数，b 为偶数，GCD(a,b)=GCD(a,b/2) 若 a 为偶数，b 为奇数，GCD(a, 查看详情

bzoj1877:[sdoi2009]晨跑

二次联通门: BZOJ1877:[SDOI2009]晨跑     /*BZOJ1877:[SDOI2009]晨跑拆点+费用流*/#include<cstdio>#include<iostream>#definergregisterinlinevoidread(int&n){rgcharc=getchar() 查看详情

[bzoj1877][sdoi2009]晨跑

1877:[SDOI2009]晨跑TimeLimit: 4Sec  MemoryLimit: 64MBSubmit: 2688  Solved: 1441[Submit][Status][Discuss]DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目 查看详情

bzoj：1877:[sdoi2009]晨跑

题解：最小费用流；拆点法；#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<queue>usingnamespacestd;constintmaxn=1000;constintinf=100000000;intn,m;inttotn,s, 查看详情

bzoj1880:[sdoi2009]elaxia的路线

1880:[Sdoi2009]Elaxia的路线TimeLimit: 4Sec  MemoryLimit: 64MBSubmit: 1035  Solved: 412[Submit][Status][Discuss]Description最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了 查看详情

bzoj1877:[sdoi2009]晨跑

BZOJ1877:[SDOI2009]晨跑DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街... 查看详情

bzoj1875[sdoi2009]hh去散步

题面：1875:[SDOI2009]HH去散步TimeLimit: 20Sec  MemoryLimit: 64MBSubmit: 1750  Solved: 851[Submit][Status][Discuss]DescriptionHH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内， 查看详情

bzoj1878[sdoi2009]hh的项链

1878:[SDOI2009]HH的项链TimeLimit: 4Sec  MemoryLimit: 64MBSubmit: 3199  Solved: 1611[Submit][Status][Discuss]DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他 查看详情

[bzoj1878][sdoi2009]hh的项链

1878:[SDOI2009]HH的项链TimeLimit:4Sec  MemoryLimit:64MBSubmit:4645  Solved:2302[Submit][Status][Discuss]DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思... 查看详情

bzoj1227:[sdoi2009]虔诚的墓主人

1#include<iostream>2#include<cstdio>3#include<algorithm>4#definelllonglong5#defineP2147483648LL6usingnamespacestd;7intn,m,w,K,H[200001];8llc[100001][11],tr[200001],ans;9structdata{in 查看详情

bzoj1875sdoi2009hh去散步

1875:[SDOI2009]HH去散步TimeLimit:20SecMemoryLimit:64MBSubmit:932Solved:424[Submit][Status][Discuss]DescriptionHH有个一成不变的习惯，喜欢饭后百步走。所谓百步走。就是散步。就是在一定的时间内，走过一定的距离。可是同一时候HH又是个喜欢变化的... 查看详情

bzoj-1875:[sdoi2009]hh去散步(矩阵快速幂)

1875:[SDOI2009]HH去散步TimeLimit: 20Sec  MemoryLimit: 64MBSubmit: 1999  Solved: 980[​​Submit​​​][​​Status​​​][​​Discuss​​]DescriptionHH有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步 查看详情

bzoj1227:[sdoi2009]虔诚的墓主人

1227:[SDOI2009]虔诚的墓主人TimeLimit:5Sec  MemoryLimit:259MBSubmit:1306  Solved:615[Submit][Status][Discuss]Description小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块... 查看详情

[bzoj1878][sdoi2009]hh的项链

[BZOJ1878][SDOI2009]HH的项链试题描述HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来... 查看详情

[bzoj1878][sdoi2009]hh的项链(树状数组+离线)

1878:[SDOI2009]HH的项链TimeLimit: 4Sec  MemoryLimit: 64MBSubmit: 3210  Solved: 1619[Submit][Status][Discuss]DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他 查看详情

bzoj-1878:[sdoi2009]hh的项链(莫队算法)

1878:[SDOI2009]HH的项链TimeLimit: 4Sec  MemoryLimit: 64MBSubmit: 4857  Solved: 2401[Submit][Status][Discuss]DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他 查看详情

[bzoj1226][sdoi2009]学校食堂dining

[BZOJ1226][SDOI2009]学校食堂Dining试题描述小F的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味... 查看详情