`
lovnet
  • 浏览: 6671642 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

URAL 1204 Idempotents(扩展欧几里得)

 
阅读更多

题目链接:Click here~~

题意:

给你一个数 n,保证 n 是两个素数 p、q 相乘的乘积,问存在几个 x ,使得 x*x = x (mod n)。(x < n)

解题思路:

首先要弄懂符号 (mod n) 的意思,若 a = b(mod n),意思是 a 和 b 分别除以 c 以后余数相同。

这种式子一般可以写成 a + k*n = b的形式。

于是本题等价于求方程 x*x + k*n = x 的解。

可以将方程化简成这样的形式: k = x*(x-1) / (p*q).(k 为任意整数)。

1、当 k 为 0 时,x = 0 或 x = 1。且这两组解一定存在。

2、当 k 不为 0 时,x 和 x-1 中必定存在 p 和 q 这两个素因子,且各至多存在一个。

反证法:若 x 中存在 p 和 q 这两个素因子,则 x >= p*q ,即 x >= n,与 x < n 矛盾。


所以解只有两种情况:(1) x 中存在因子 p,x-1 中存在因子 q;(2) x 中存在因子 q,x-1 中存在因子 p。

对于情况(1),相当于给了两个式子 x%p=0 和 (x-1)%q=0。

也就是 x - pi = 0 和 x - qj = 1。于是得到了 pi - qj = 1。(gcd(p,q) = 1)

然后运用扩展欧几里得算法可以求得 i,j 的某组解,再将它适当调整到正值即可。

同理可解出情况(2)。


#include <stdio.h>
#include <algorithm>
using namespace std;

#define N 35000

bool Not_Prime[N];

int P[4222];

void Prime()
{
    int top = -1;
    for(int i=2;i<N;i++)
        if(!Not_Prime[i])
        {
            P[++top] = i;
            for(int j=i+i;j<N;j+=i)
                Not_Prime[j] = true;
        }
}

void ExGcd(int a,int b,int &x,int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return ;
    }
    ExGcd(b,a%b,x,y);
    int t = x;
    x = y;
    y = t - a/b*y;
}

int main()
{
    int z,p,q,x,y,n,X1,X2;
    scanf("%d",&z);
    Prime();
    while(z--)
    {
        scanf("%d",&n);
        for(int i=0;;i++)
        {
            if(n%P[i] == 0)
            {
                p = P[i];
                q = n/P[i];
                break;
            }
        }
        ExGcd(p,q,x,y);
        X1 = x<0 ? p*x+p*q : p*x;
        ExGcd(q,p,x,y);
        X2 = x<0 ? q*x+p*q : q*x;
        printf("%d %d %d %d\n",0,1,min(X1,X2),max(X1,X2));
    }
	return 0;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics