l

今天药忘吃喽~ 2022-08-17 13:27 179阅读 0赞

## l ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K \* M % N = 1，如果有多个满足条件的，输出最小的。

## 输入 ##

输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)

## 输出 ##

输出一个数K，满足0 < K < N且K \* M % N = 1，如果有多个满足条件的，输出最小的。

## 示例输入 ##

2 3

## 示例输出 ##

2

## 提示 ##

## 来源 ##

Rocky

## 示例程序 ##

#include<stdio.h>  
    long long x,y,d;  
    long long gcd(long long a,long long b)  
    {  
        return a?gcd(b%a,a):b;  
    }  
    void gcd(long long a,long long b,long long &d,long long &x,long long &y)  
    {  
        if(!b)  
        {  
            d=a;  
            x=1;  
            y=0;  
        }  
        else  
        {  
            gcd(b,a%b,d,y,x);  
            y-=x*(a/b);  
        }  
    }  
    int main()  
    {  
        long long i,j,n,m,k,t;  
        while(scanf("%lld %lld",&m,&n)!=EOF)  
        {  
            d=gcd(m,n);  
            gcd(m,n,d,x,y);  
            x=((x%n)+n)%n;  
            printf("%lld\n",x);  
        }  
      
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关 L1，L2，L3 Cache缓存原理

一、介绍 CPU缓存（Cache Memory）也被称为Cache，是存储器子系统的组成部分，存放着程序经常使用的指令和数据。从广义的角度上看，Cache是快设备为了缓解

落日映苍穹つ/ 2024年03月22日 16:40/ 0 赞/ 47 阅读

相关 L1和L2正则化和L1和L2损失

[L1和L2正则化][L1_L2] [https://blog.csdn.net/weixin\_43216017/article/details/88046435][L1

╰+哭是因爲堅強的太久メ/ 2023年01月13日 10:00/ 0 赞/ 154 阅读

相关 strtok, _strtok_l, wcstok, _wcstok_l, _mbstok, _mbstok_l分词函数

// crt_strtok.c // compile with: /W3 // In this program, a loop uses strtok

喜欢ヅ旅行/ 2022年08月27日 15:49/ 0 赞/ 176 阅读

相关 l

l Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给出2个数M和N(M < N)，

今天药忘吃喽~/ 2022年08月17日 13:27/ 0 赞/ 179 阅读

相关 l0-Norm, l1-Norm, l2-Norm, … , l-infinity Norm

原文链接：[http://blog.csdn.net/u011650143/article/details/54695180][http_blog.csdn.net_u0116

Love The Way You Lie/ 2022年06月06日 11:44/ 0 赞/ 205 阅读

相关 Given a singly linked list L: L 0→L 1→…→L n-1→L n, reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…

> 题目描述 Given a singly linked list L: L 0→L 1→…→L n-1→L n, reorder it to: L 0→L n →L 1

Bertha 。/ 2022年05月26日 04:25/ 0 赞/ 201 阅读

相关 L - Median

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

川长思鸟来/ 2022年01月29日 03:04/ 0 赞/ 195 阅读

相关 L255

If a farmer wishes to succeed, he must try to keep a wide gap between his consumption an

拼搏现实的明天。/ 2021年12月23日 08:29/ 0 赞/ 92 阅读

相关 L224

Astronomers have revealed details of mysterious signals emanating from a distant galaxy,

古城微笑少年丶/ 2021年12月23日 08:27/ 0 赞/ 122 阅读

相关 CPU缓存L1/L2/L3工作原理

点击上方“开源Linux”，选择“设为星标” 回复“学习”获取独家整理的学习资料！ ![format_png][] 一、前言在过去的几年中，计算机处理器取得了相

╰+哭是因爲堅強的太久メ/ 2021年07月27日 00:49/ 0 赞/ 325 阅读