广州seo网站管理,360免费建站教程,网站建设公司的公司哪家好,用php内容做电商网站题目
给定n组数据ai, bi , mi#xff0c;对于每组数求出一个xi#xff0c;使其满足ai * xibi (mod mi)#xff0c;如果无解则输出impossible。
输入格式
第一行包含整数n。 接下来n行#xff0c;每行包含一组数据ai , bi , mi。
输出格式
输出共n行#xff0c;每组数…题目
给定n组数据ai, bi , mi对于每组数求出一个xi使其满足ai * xibi (mod mi)如果无解则输出impossible。
输入格式
第一行包含整数n。 接下来n行每行包含一组数据ai , bi , mi。
输出格式
输出共n行每组数据输出一个整数表示一个满足条件的xi如果无解则输出impossible。 每组数据结果占一行结果可能不唯一输出任意一个满足条件的结果均可。 输出答案必须在int范围之内。
数据范围
1 ≤n ≤105 1 ≤ai , bi, mi≤2* 109
输入样例:
2
2 3 64 3 5*输出样例
impossible
-3题解
#include iostream
using namespace std;
int exgcd(int aint bint x, int y)
{if (!b){ x 1, y 0;return a; }int d exgcd(b,a % b y, x);y - a / b * x;return d;
}
int main( )
{int n;scanf(%d,n);while (n -- ){int a, b, m;scanf( %d%d%d, abm);int x, y;int d exgcd(a, m, x, y);if (b % d)puts( impossible ) ;else printf(%din, (LL)x * (b / d) % m);} return 0;思路
利用扩展欧几里得算法变形即可得到 如下图
