首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

ZOJ 3562 Alice's Sequence I 中国剩下定理 不互质

2013-10-31 
ZOJ 3562Alices Sequence I 中国剩余定理 不互质不互质的中国剩余定理就不能直接方程组那样搞了两个两个的

ZOJ 3562 Alice's Sequence I 中国剩余定理 不互质

不互质的中国剩余定理

就不能直接方程组那样搞了

两个两个的搞就行

然后求出的解之间的间隔是固定的。


#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cstdlib>#include <cmath>#include <map>#include <sstream>#include <queue>#include <vector>#define MAXN 111111#define MAXM 211111#define eps 1e-8#define INF 1000000001using namespace std;typedef long long LL;LL ExGcd(LL a, LL b, LL &x, LL &y){    if(b == 0)    {        x = 1;        y = 0;        return a;    }    LL r = ExGcd(b, a % b, x, y);    LL t = x;    x = y;    y = t - a / b * y;    return r;}LL a[111], m[111], l, r;int n;int main(){    while(scanf("%d", &n) != EOF)    {        LL M ;        for(int i = 0; i < n; i++)            scanf("%lld", &m[i]);        int flag = 0;        for(int i = 0; i < n; i++) scanf("%lld", &a[i]);        for(int i = 0; i < n; i++)        {            if(a[i] >= m[i]) flag = 1;        }        scanf("%lld%lld", &l, &r);        LL a1, b1, a2, b2;        a1 = m[0], b1 = a[0];        for(int i = 1; i < n; i++)        {            a2 = m[i], b2 = a[i];            if(flag) continue;            LL x, y;            LL g = ExGcd(a1, a2, x, y);            LL c = b2 - b1;            if(c % g)            {                flag = 1;                break;            }            LL tmp = a2 / g;            c /= g;            x = (x * c % tmp + tmp) % tmp;            b1 = a1 * x + b1;            a1 = a1 * tmp;        }        if(flag) printf("0\n");        else        {            LL now = b1 % a1;            M = a1;            if(l > now)            {                now = (l - now) / M * M + now;                while(now < l) now += M;            }            LL cnt = 0;            LL tmp = now;            if(r >= now) cnt = (r - now) / M + 1;            printf("%lld\n", cnt);            if(cnt > 100) cnt = 100;            int k = 0;            now = tmp;            while(now <= r)            {                k++;                printf("%lld", now);                if(k < cnt) printf(" ");                else printf("\n");                if(k == cnt) break;                now += M;            }        }    }    return 0;}


热点排行