ProjectEuler – Diophantine reciprocals (数论, 数学)

最近真是发现这个网站越来越好了!

Diophantine reciprocals I:

题意:

对于一个n : f(n)的值为所有的(x,y)满足以下条件:

Screenshot.png
丢番图

求 min_n 满足f(min_n) > 1000

分析:

我们移项发现了以下:

Screenshot.png

所以不难发现 n < x 而且 n < y

那么我们不妨设 n = x + a = y +b;

就有以下:

Screenshot.png

化简发现Screenshot.png

那么我们其实就知道了答案是:

Screenshot.png
答案

然后还是有点慢…所以我们需要在算法里加入以下:

  1. 线性筛质数
  2. 利用下面的公式:

Screenshot.png

答案:180180

代码:

代码

Diophantine reciprocals II

题意:

加强版的上一题, 变成找最小的 n , 使得 f(n) > 4e6!

分析:

我们可以还是利用这个公式, 而且这个n其实可以贪心的构造, 所以只要选前 20 个左右的质数来DFS就好了

Screenshot

代码:

代码

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define P pair<int,int>
#define R register
using namespace std;

const int N = 10005000;
const LL INF = 0x3f3f3f3f3f3f3f;
LL ans = INF;

int prim[20] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
void DFS(LL num, LL res, int upper, int link)
{
    if(link > 17 ) return ;
    if(num > ans) return ;
    if(res > 7999999) return (void)( ans = min(ans, num));
    LL now = 1;
    for(int j = upper; j >= 1; j--) now *= 1LL * prim[link];
    for(int j = upper; j >= 1; j--)
    {
        if((double) num * now < (double) ans)
            DFS(num * now, res * ((j << 1) + 1), j, link + 1);
        now /= prim[link];
    }
}

signed main()
{
    DFS(1, 1, 20, 1);
    printf("%lld\n", ans);
    return 0;
}

Hope that you will enjoy it! 🙂

One Reply to “ProjectEuler – Diophantine reciprocals (数论, 数学)”

发表评论

电子邮件地址不会被公开。 必填项已用*标注