首页 > 代码库 > hdoj 1576
hdoj 1576
//1Y真是爽啊
题意：要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
分析：根据题意a=b*x a=m*y+n
得b*x-m*y=n;
根据exgcd求得一组解x，y
#include "stdio.h"#include "string.h"#include "algorithm"#define m 9973using namespace std;int exgcd(int a,int b,int &d,int &x,int &y){ if(!b) {d=a;x=1;y=0;} else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}}int gcd(int a,int b){ if(a%b==0) return b; return gcd(b,a%b);}int main(){ int x0,y0,x,y; int g,t; int n,a,b,m1,b1; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&b); g=gcd(b,m); m1=m/g; b1=b/g; exgcd(b,m,g,x0,y0); x0=x0*(n/g); x=x0+m1; while(x<0) x+=m; printf("%d\n",x%m); } return 0;}
hdoj 1576
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。