关键词：
整数性质
- 描述
-
我们知道，在数学中，对于任意两个正整数a和b，必定存在一对整数s、t使得sa+tb=gcd(a,b)。
- 输入
- 多组测试数据。
每组数据输入两个非负整数a和b且a+b>0且a不等于b。
其中0<=a,b<100000。 - 输出
- 输出满足条件的 s 和 t 。
- 样例输入
-
2 4 3 8 737 635
- 样例输出
-
1 0 3 -1 193 -224
- 提示
运用欧几里得定理求得的才是正确答案。
http://baike.sogou.com/v5706906.htm?fromTitle=扩展欧几里德算法
看完之后就明白了
#include <stdio.h>
#include <math.h>
void extends_Gcd(int a,int b,int &s,int &t)
if(!b)
s=1;
t=0;
return ;
extends_Gcd(b,a%b,s,t);
int temp=s;
s=t;
t=temp-a/b*t;
int main()
int a,b;
while(~scanf("%d%d",&a,&b))
int s=0,t=0;
extends_Gcd(a,b,s,t);
printf("%d %d\n",s,t);
return 0;
不要用cin cout 会超时。。
nyoj-0708-ones(代码片段)
nyoj-0708-ones题意：用1,+,*,(,).这四个符号组成表达式表达数s(0<=s<=10000),且1最少时1的的个数状态转移方程:dp[i]=min(dp[i-1]+1,dp[j]+dp[i-j]);代码：#include<bits/stdc++.h>usingnamespacestd;constintN=100001;intdp[N];intmain() 查看详情
nyoj圈水池(代码片段)
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>usingnamespacestd;structnodeintx,y;;nodevex[1000];//存入的所有的点nodestackk[1000];//凸包中所有 查看详情
nyoj单词拼接(代码片段)
#include<iostream>#include<string>#include<string.h>#include<queue>#include<stdio.h>#include<math.h>#include<algorithm>usingnamespacestd;#defineMAX2005intfirs 查看详情
nyoj484-thefamousclock(代码片段)
484-TheFamousClock内存限制:64MB时间限制:1000ms特判:No通过数:2提交数:2难度:1题目描述:Mr.B,Mr.GandMr.MarenowinWarsaw,Poland,forthe2012’sACM-ICPCWorldFinalsContest.They’vedecidedtotakea5hourstrainingeverydaybeforethecontest.A 查看详情
nyoj-158-省赛来了（组合数）(代码片段)
题目链接1/*2Name:nyoj-158-省赛来了3Copyright:4Author:5Date:2018/4/2517:07:226Description:7暴力，秒天秒地8*/9#include<iostream>10#include<cstdio>11usingnamespacestd;12longlongc[1000][1000];13intmain()141 查看详情
nyoj棋盘覆盖(代码片段)
数字很大，要用大数乘法。 #include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>usingnamespacestd;chars1[1000];chars2[10];char*bignum(char*num1,c 查看详情
nyoj-211-cowcontest(floyd算法)(代码片段)
题目链接1/*2Name:nyoj-211-CowContest3Copyright:4Author:5Date:2018/4/2721:02:066Description:7floyd算法8大佬的惊奇思路9*/10#include<iostream>11#include<cstdio>12#include<cstring>13usingnamespacestd 查看详情
nyoj61传纸条(代码片段)
双线DP#include<iostream>#include<algorithm>#include<ctype.h>#include<string>#include<string.h>#include<vector>#include<queue>usingnamespacestd;intdp[110][55][55 查看详情
nyoj迷宫寻宝(代码片段)
#include<iostream>#include<string>#include<string.h>#include<queue>#include<stdio.h>#include<math.h>#include<algorithm>usingnamespacestd;chard[30][30];inta[5] 查看详情
nyoj208+poj1456supermarket(贪心)(代码片段)
Supermarket时间限制：1000ms | 内存限制：65535KB难度：4 描述AsupermarkethasasetProdofproductsonsale.Itearnsaprofitpxforeachproductx∈Prodsoldbyadeadlinedxthatismeasuredasanintegralnumberoftimeunitsstart 查看详情
nyoj会场安排问题(代码片段)
#include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>usingnamespacestd;structHYintu,v;hy[10005];boolcmp(HYa,HYb)if(a.v==b.v)returna.u 查看详情
nyoj-115-城市平乱（dijkstra算法）(代码片段)
题目链接1/*2Name:nyoj-115-城市平乱3Copyright:4Author:5Date:2018/4/2517:28:066Description:7dijkstra模板题8枚举从部队所在的城市到叛乱城市取最小值9*/10#include<iostream>11#include<cstdio>12#include<cstring>13# 查看详情
nyoj5binarystringmatching(代码片段)
BinaryStringMatching时间限制：3000ms | 内存限制：65535KB|难度：3 描述 GiventwostringsAandB,whosealphabetconsistonly‘0’and‘1’.YourtaskisonlytotellhowmanytimesdoesAappearasasubstringofB?Forexample,thet 查看详情
nyoj鏂规鏁伴噺(代码片段)
鏍囩锛?ahref='http://www.mamicode.com/so/1/end'title='end'>end stdio.h == wrong 閫掓帹 style || &n 查看详情
nyoj开心的小明(代码片段)
#include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>usingnamespacestd;intd[30][30005];//d[i][j]i件中，j重量的物品，价格最高intv[30],w[30];intMax(int 查看详情
nyoj疯牛(代码片段)
疯牛时间限制：1000 ms | 内存限制：65535 KB难度：4 描述农夫John建造了一座很长的畜栏，它包括N(2<=N<=100,000)个隔间，这些小隔间依次编号为x1,...,xN(0<=xi<=1,000,000,000).但是，John的C(2<=C<=N)头牛们并不喜... 查看详情
nyoj72-financialmanagement(求和÷12.0)(代码片段)
72-FinancialManagement内存限制:64MB时间限制:3000ms特判:No通过数:7提交数:12难度:1题目描述:Larrygraduatedthisyearandfinallyhasajob.He‘smakingalotofmoney,butsomehowneverseemstohaveenough.Larryhasdecidedthatheneedstograbholdof 查看详情
nyoj非洲小孩(代码片段)
非洲小孩时间限制：1000 ms | 内存限制：65535 KB难度：2 描述家住非洲的小孩，都很黑。为什么呢？第一，他们地处热带，太阳辐射严重。第二，他们不经常洗澡。（常年缺水，怎么洗澡。）现在，在一个非洲部... 查看详情