关于最后结果的处理
字写得有点丑，请见谅
C++ AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
int N,M;
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x = 1,y = 0;
return a;
}
int d = exgcd(b,a%b,x,y);
int tmp = x;
x = y;
y = tmp -a/b*y;
return d;
}
int main(){
int i,j,k;
cin>>N;
for(i = 1;i<=N;i++){
int a,b,m;
scanf("%d %d %d",&a,&b,&m);
int x,y;
int d = exgcd(a,m,x,y);
if(b%d==0){
int t = b/d;
printf("%d\n",((long long)x*t%(m/d)+(m/d))%(m/d));
}
else
printf("impossible\n");
}
return 0;
}
你写那么多头文件干嘛 怪吓人的
哈哈，雀氏
这字要是丑 那我的字就是画了。。。
a/gcd与m/gcd互质，则$x-x_0$必然包含因子m/gcd,否则左边就没有m/gcd这个因子了
太棒了！！！！！！！怒赞！！！！！
为什么%m，可以理解为：为了防止所求某特解x0是一个很大的数，其通解是乘以一定倍数后（b/gad(a,b)）可能会爆，最后取模可以求最小的解
大佬orz，看不懂，T~T
x*t%(m/d)+(m/d))%(m/d),,能解释一下吗
左右同乘 d/b 即可转化为：a * x * d/b + m * y1 * d /b = b * d /b =d
x*t得到x0,然后剩下的是为了求最小正整数解
所以为什么最后要%m
假设某个特解为ax0+by0=n；
那这个也等同于 a（x0+bt）+b（y0-at）=n;
x的通解为 x=x0+b*t;
最后取模可以求最小的解
写的很好,a和m互质的充分必要条件是存在x和y使得ax+by=1ax+by=1,除gcd(a,m)就可以得到ax+by=1ax+by=1,∴a/gcd(a,m)与m/gcd(a,m)互质
谁说这字丑的，这字可太棒了！
样例就有问题请教
y总的输出
这里的代码
词组数据为何和y总的输出不一致
为什么要%m?可以试试不%m的样例，x实际上有无穷多个，但题目要求是输出int范围内的任意一个，但当输入数据很大时，不同满足题目要求的x在int范围内可能相差特别特别大，导致一个在int范围内，一个在int范围外，因此需要对结果modm,将答案规定在输入m的正负范围内，就会满足在int范围内，这样依然满足题目要求的 a * x mod m == a * (x mod m) mod m
NB
最后三行疑似x和x0写反
按这公式往下推，那x不应该是等于x0-那一串吗
大佬，求得了x的最小周期性解，但最后x不还要乘以(b/d)吗，乘完以后的周期性为什么也是通过%(m/d) ？
为什么最后取余还要再除以个d呢，我交了下%m也能ac
图片怎么上传啊
写题解或者打卡的文字编辑框右上角点上传图片按钮
%%%%%%%%%%%%%%
TQL