杭州白富美征婚了
in Solutions with 2 comments

杭州白富美征婚了

in Solutions with 2 comments

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
  2. Amoxicillin Expiration Date Viagra Pfizer Manufacturers Buy Cialis Levitra Internet Online Drugstore Flagyl Pay By Money Order Priligy Or Viagra

    Reply