对角线穿过 N 个正方形的不同矩形的数量

Question

我正在解决 CS 问题，几乎不需要帮助。我有数字 N，如果矩形在大小为 1x1 的矩形上拆分，我需要计算对角线在 N 个正方形中通过的不同矩形的数量。这张图帮你理解。

这张图片显示了 N = 4 时的所有 4 种组合，实际上对角线穿过 4 个正方形的矩形的大小为 1x4、2x3、4x2 和 4x4。

如果我们给出矩形的两个尺寸，我找到了公式：

A + B - gcd(A,B)

因为 N<=10^6，我上升到 10^6 并为每个 N 检查 N 的约数，其复杂度为 O(Nsqrt(N))，因为A 的约数是 gcd(A,B)i 求解方程组 q 是 A 的除数，q 是 gcd(A,B) A+B-q=N 和 gcd(A,B)=q 我在 O(Nsqrt(N)*log(N)) 中解决了这个问题我假设 log(N) 是找到两个数字的 gcd 的时间。

因为时间限制是 3 秒所以它按时失败了。我需要有关优化解决方案的帮助。

更新：这是我的代码：

#include <bits/stdc++.h>

#define ll long long
using namespace std; 
int a;

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

bool valid(int n, int m, int gc, int a) {
    if(n+m-gc==a) return true;
    return false;
}

int main() {
cin>>a;

int counter=0;
for(int i=1;i<=a/2;i++) {
    for(ll j=1;j<=sqrt(i);j++) {
        if(i%j==0) {
            if(j!=i/j) {
                int m1 = a+j-i;
                int div=i/j;
                int m2 = a+div-i;
                if(valid(i, m1, j, a)) {
                    if(gcd(i, m1)==j)
                        counter++;
                }
                if(valid(i, m2, i/j, a)) {
                    if(gcd(i,m2)==i/j)
                        counter++;
                }

            }
            else {
                int m1 = a+j-i;
                if(valid(i, m1, j, a)) {
                    if(gcd(i, m1)==j)
                        counter++;
                }
            }
        }
    }
}
cout<<counter+1;
return 0;
}

提前致谢。

Answer 1

虽然 O(n*sqrt(n)*log(n)) 对于 n <= 10^6 听起来有点多，而且您可能需要稍微好一点的算法，但您的代码支持一些优化：

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

摆脱交换，没有它也能正常工作。

当你这样做的时候，也摆脱递归：

int gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }

    return a;
}

下一个：

for(int i=1;i<=a/2;i++) {
    for(ll j=1;j<=sqrt(i);j++) {

在各自的循环之外计算 a/2 和 sqrt(i)。无需在每次迭代时计算它。编译器可能会或可能不会足够聪明（或设置）自己执行此操作，但您不应该依赖它，尤其是在在线判断设置中。

您还可以预先计算 i / j 进一步向下，以免每次都重新计算。很多除法可能会很慢。

接下来，j真的需要long long吗？ i 是一个 int，j 上升到它的平方根。所以你不需要 long long 代替 j，使用 int.

对角线穿过 N 个正方形的不同矩形的数量

Number of distinct rectangles in which diagonal is passing in N squares

algorithm

computer-science

combinatorics