1

给定整数 N 和 M，找到有序对 (a, b) 的数量，使得 1≤a <b≤N 并且 ((M mod a) mod b) = ((M mod b) mod a)。

输入 第一行包含一个整数 T，即测试用例的数量。然后是测试用例。

每个测试用例的唯一一行包含两个整数 N、M。

输出 对于每个测试用例，在一行中输出问题的答案。

约束 1≤T≤1000

2≤N≤10 ^ 6

1≤M≤5⋅10 ^ 5

所有测试用例的 N 总和不超过 10 ^ 6

我尝试过 O (N ^ 2) 方法，但它提供了 TLE。需要一种新方法或任何想法

import java.util.Scanner;

class test {
    public static void main(String[] args) {
        try {
            Scanner scn = new Scanner(System.in);
            int testCase = scn.nextInt();
            for (int i = 0; i < testCase; i++) {
                int n = scn.nextInt();
                int m = scn.nextInt();
                int count = 0;
                for (int j = 1; j < n; j++) {
                    for (int k = j + 1; k <= n; k++) {
                        if (((m % j) % k) == ((m % k) % j)) {
                            // System.out.print(j+" "+k);
                            // System.out.println();
                            count++;
                        }

                    }
                }
                System.out.println(count);

            }
        } catch (Exception e) {
            return;
        }
    }
}
4

1 回答 1

2

我可以看到一些改进。首先，由于 a<b，(M mob a) mod b = M mod a

所以我们要检查是否M mod a = (M mod b) mod a，但这意味着a除以(M - (M mod b))=((M div b) * b)

总而言之，我们必须遍历所有 b=1,...,n 并且对于它们中的每一个，我们必须计算 ((M div b) * b) 的除数小于 b。

改进之处在于 ((M div b) * b) 与 b 相当，当我们寻找 ((M div b) * b) 的除数时，我们可以停在它的平方根处。

一个可能的实现（我已经删除了测试用例）是这个

class Test {
public static void main(String[] args) {
    try {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int m = scn.nextInt();
        int count = 0;
        for (int j = 1; j < n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (((m % j) % k) == ((m % k) % j)) {
                    //System.out.print(j+" "+k);
                    //System.out.println();
                    count++;
                }

            }
        }
        System.out.println(count);
        count=0;
        for (int b = 1; b <= n; b++) {
            //System.out.println((m/b)*b);
            count += countDivisors(m, b);
        }
        System.out.println(count);

    } catch (Exception e) {
        return;
    }
}

private static int countDivisors(int m,  int b) {
    int count=0;
    int val = ((m/b)*b);
    int mi = Math.min((int)Math.sqrt(val), b-1);
    if(mi == 0)
        return (b-1);
    for(int a=1; a<=mi; a++) {
        if(val % a == 0) {
            count++;
            int aa=val/a;
            if(aa>a && aa < b) {
                count++;
            }
        }
    }
    return count;
}

}

于 2021-05-11T13:46:38.970 回答