正文 

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

bzoj1876[sdoi2009]supergcd

zbtrs zbtrs     2022-09-15     554

关键词：

1876: [SDOI2009]SuperGCD

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 3744  Solved: 1349
[Submit][Status][Discuss]

Description

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

Input

共两行： 第一行：一个数A。 第二行：一个数B。
0 < A , B ≤ 10 ^ 10000。

Output

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

Sample Input

12
54

Sample Output

6

HINT

 

Source

Day1

分析：这道题是一道非常烦人的高精度问题，求gcd谁都会，但是直接用欧几里得算法，高精度取模直接gg，而且还是压位的，打出来估计要半天.那么换一种方法：更相减损术：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。        ----摘自百度百科
也就是说我们只需要设计乘法，除法和减法就可以了。高精度算法就相当于模拟我们算术一样，只不过用程序跑而已，步骤是先操作，再进位、补位，最后看数组的长度有没有改变.
这道题一定要压位来处理，不然会tle,压位后的操作与没有压位差不多，只不过mod的数变了，以前是逢10进1，现在是逢n进1.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>

using namespace std;

const int mod = 100000000;

int tot;

struct node
{
    int x[2010], len;
}a,b;

void read(node &c)
{
    char s[10010];
    scanf("%s", s);
    int len = strlen(s),cnt = 0,chengji = 1;
    for (int i = len - 1; i >= 0; i--)
    {
        cnt = cnt + (s[i] - ‘0‘)* chengji;
        chengji *= 10;
        if ((len - i) % 8 == 0)
        {
            c.x[++c.len] = cnt;
            cnt = 0;
            chengji = 1;
        }
    }
    if (cnt != 0)
        c.x[++c.len] = cnt;
}

void div1()
{
    for (int i = a.len; i >= 1; i--)
    {
        if (a.x[i] % 2 == 1)
            a.x[i - 1] += mod;
        a.x[i] >>= 1;
    }
    while (a.x[a.len] == 0 && a.len > 1)
        a.len--;
}

void div2()
{
    for (int i = b.len; i >= 1; i--)
    {
        if (b.x[i] % 2 == 1)
            b.x[i - 1] += mod;
        b.x[i] >>= 1;
    }
    while (b.x[b.len] == 0 && b.len > 1)
        b.len--;
}

bool check()
{
    if (a.len != b.len)
        return false;
    for (int i = 1; i <= a.len; i++)
        if (a.x[i] != b.x[i])
            return false;
    return true;
}

bool cmp()
{
    if (a.len > b.len)
        return true;
    else
        if (a.len < b.len)
            return false;
    for (int i = a.len; i >= 1; i--)
    {
        if (a.x[i] > b.x[i])
            return true;
        else
            if (a.x[i] < b.x[i])
                return false;
    }
    return true;
}

void jian(node &c, node d)
{
    for (int i = 1; i <= c.len; i++)
    {
        if (c.x[i] >= d.x[i])
            c.x[i] -= d.x[i];
        else
        {
            c.x[i] = c.x[i] + mod - d.x[i];
            c.x[i + 1]--;
        }
    }
    while (c.x[c.len] == 0 && c.len > 1)
        c.len--;
}

void mul()
{
    for (int i = 1; i <= a.len; i++)
        a.x[i] <<= 1;
    for (int i = 1; i <= a.len; i++)
        if (a.x[i] >= mod)
        {
        a.x[i] -= mod;
        a.x[i + 1]++;
        }
    while (a.x[a.len + 1])
        a.len++;
}

void print()
{
    printf("%d", a.x[a.len]);
    for (int i = a.len - 1; i >= 1; i--)
        printf("%08d", a.x[i]);
    printf("
");
}

int main()
{
    read(a);
    read(b);
    while (a.x[1] % 2 == 0 && b.x[1] % 2 == 0)
    {
        tot++;
        div1();
        div2();
    }
    while (!check())
    {
        if (cmp())
            jian(a, b);
        else
            jian(b, a);
        while (a.x[1] % 2 == 0)
            div1();
        while (b.x[1] % 2 == 0)
            div2();
    }
    while (tot--)
        mul();
    print();

    return 0;
}

 

 

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的学校在城市的一个偏僻角落，所有学生都只好在学校吃饭。学校有一个食堂，虽然简陋，但食堂大厨总能做出让同学们满意的菜肴。当然，不同的人口味也不一定相同，但每个人的口味... 查看详情