url: https://ybt.ssoier.cn/problem_show.php?pid=1638

tag:
裴蜀定理，拓展欧几里得算法，数论

思路：
根据题意可以得出，y - x = b d mod n ⇒ b d - a n = y - x。所以可以先求出n与d的最大公约数，如果y - x 不能整除，说明不能到达，如果可以整除再求最小的b。用拓展欧几里得算法可以求出 x n + y d = (n,d) 的一组解，然后令该式两边同乘 （y - x）/ （n，d）可以将该式变为b d - a * n = y - x。最后求最小的d就是让其取模n / gcd的正余数。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        LL n, d, x, y, a, b;
        scanf("%lld%lld%lld%lld", &n, &d, &x, &y);
        LL gcd = exgcd(n, d, a, b);
        if ((y - x) % gcd) cout << "Impossible\n";
        else
        {
            b *= (y - x) / gcd;
            n /= gcd;
            printf("%lld\n", (b % n + n) % n);
        }
    }
    return 0;
}

url: https://www.luogu.com.cn/problem/P2568

tag:
数论，欧拉函数，筛法，前缀和

思路：
假设又两个互质的整数a, b，则gcd(a, b) = 1，那么对于任意的自然数p有gcd(a p, b p) = p。利用这个结论，对于这道题我们可以先求欧拉函数，然后求一遍gcd(a, b) = 1 的前缀和，这里求前缀和的时候注意对于1来说只有(1, 1)之后的其他组都有(a, b)和(b, a)。最后遍历每一个质数，用最大值求一个m，使得max(a, b)不超过m的每一对互质数都乘上一个质数得出一个可能的结果。将这个前缀和加到答案即可。

代码：

#include <iostream>  
#include <vector>  
using namespace std;  
const int N = 1e7 + 10;  
int n, phi[N];  
long long sum[N];  
bool st[N];  
long long res;  
vector<int> primes;  
int main()  
{  
    cin >> n;  
    for (int i = 1; i <= n; i ++) phi[i] = i;  
    st[0] = st[1] = true;  
    for (int i = 2; i <= n; i ++)  
    {  
        if (!st[i])  
        {  
            primes.push_back(i);  
            phi[i] = i - 1;  
        }  
        for (int p : primes)  
        {  
            if (p * i > n) break;  
            st[p * i] = true;  
            if (i % p == 0)  
            {  
                phi[i * p] = phi[i] * p;  
                break;  
            }  
            else  
            {  
                phi[i * p] = phi[i] * (p - 1);  
            }  
        }  
    }  
    sum[1] = 1;  
    for (int i = 2; i <= n; i ++)  
    {  
        sum[i] = sum[i - 1] + phi[i] * 2;  
    }  
    for (int p : primes)  
    {  
        int m = n / p;  
        res += sum[m];  
    }  
    cout << res << endl;  
}