c++ 给定整数C和N(c ≤ n ≤ 10^9)，求出对i，j(n>= i>= j>= 1)的数量，其中gcd(i，j)== C

x33g5p2x 于 2023-02-06 发布在其他

关注(0)|答案(1)|浏览(122)

给定整数C和N（c ≤ n ≤ 10^9），求出对i，j（n〉= i〉= j〉= 1）的数量，其中gcd（i，j）== C

long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void solve(int tt){
    int c,n;
    cin >> c >> n;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            if(gcd(i,j) == c) ans++;
        }
    }
    cout << ans;
    return;
}

这是越来越超时，我已经尝试了各种不同的方法来尝试和修复它-没有任何工作...有人知道的代码来优化这一点吗？（输出%100000007）

c++

来源：https://stackoverflow.com/questions/75316563/given-integers-c-and-n-c-n-109-find-the-amount-of-pairs-i-j-n-i

1条答案

按热度按时间

pgky5nke1#

给定整数C和N（c〈= n〈= 10^9），求i，j（n〉= i〉= j〉= 1）对的个数，其中gcd（i，j）== C
我们可以用C除一切得到：
有多少个整数i和j满足：2〈= j〈i〈= n/c，并且是互质的？
让我们来检查几个：

n/c   count (new pairs listed in parens)
<=2   0
3     1  (2,3) 
4     2  (3,4)
5     5  (2,5), (3,5), (4,5)
6     6  (5,6)
7     11 (2,7), (3,7), (4,7), (5,7), (6,7)
8     14 (3,8), (5,8), (7,8)
9     19 (2,9), (4,9), (5,9), (7,9), (8,9)

每次增加i时，我们可以将它与j〉= 2中所有不具有相同因子的较小值配对，对于素数，这就是j〉= 2中所有较小值。
这是https://oeis.org/A015613。

赞(0）回复(0）举报 2023-02-06

我来回答

c++ 给定整数C和N(c ≤ n ≤ 10^9)，求出对i，j(n>= i>= j>= 1)的数量，其中gcd(i，j)== C

1条答案

相关问题

热门标签

最新问答