杭州白富美征婚了
in Solutions with 1 comment

杭州白富美征婚了

in Solutions with 1 comment

4月1号的奇闻

bfm

所以做一下
思路比较简单
她给的那个数是N,既然N由两个素数相乘,根据欧拉定理
$$\phi(N)=(p-1)(q-1)=p*q-(p+q)-1$$
我们可以在O(n)时间内先把phi(N)求出来,这样可以得到p+q
$$p+q=p*q-1-\phi(N)---(1)$$
p+qpq得到p-q
$$p-q=\sqrt{(p+q)^2-4pq}---(2)$$
$$p=((1)+(2))/2$$
$$q=((1)-(2))/2$$
这样便获得了p,q的值

至于第二问,循环那999个值用这个方式再找一遍就可以了。

#include<bits/stdc++.h>
using namespace std;
//欧拉函数
int64_t phi(int64_t n)
{
    int64_t i;
    int64_t ans;
    ans=1;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans*=(i-1);
            n/=i;
            while(n%i==0)
            {
                ans*=i;
                n/=i;
            }
        }
    }
    if(n!=1)ans*=n-1;
    return ans;
}
//素数分解
void solution(int64_t pq,int64_t* p,int64_t* q)
{
    int64_t phipq=phi(pq);
    int64_t pAddq = pq + 1 - phipq;
    int64_t pMinusq = sqrt(pAddq * pAddq - 4 * pq);
    *p = (pAddq + pMinusq) / 2;
    *q = (pAddq - pMinusq) / 2;
}

int main()
{
    int64_t base = 6541367000;
    for (int64_t i = 0; i <= 999;++i)
    {
        int64_t tmp = base+i;
        int64_t *p = (int64_t *)malloc(sizeof(int64_t));
        int64_t *q = (int64_t *)malloc(sizeof(int64_t));
        solution(tmp, p, q);
        //验证并求解
        if(((*p)*(*q)==tmp)&&(phi((*p)*(*q))==((*p-1)*(*q-1))&&phi(*p)==(*p-1)&&phi(*q)==(*q-1)))
            cout << (*p) << " " << (*q) <<" "<< (*p) * (*q) << endl;
        free(p);
        free(q);
    }
    system("pause");
    return 0;
}
Responses
  1. Cialis Lilly Costo How To Take Viagra Cephalexin Flu And Nasal Infections [url=http://lowpricecial.com]cheapest cialis 20mg[/url] Viagra Vente Quebec Cafagote Diflucan For Sale Online

    Reply