Satisfactory Pairs HackerRank - pairs-again——预处理＋不定长数组应用-蒲公英云

Satisfactory Pairs HackerRank - pairs-again——预处理＋不定长数组应用

Think:
1题意：输入n, 求(a, b)满足a < b 且存在x, y使得x*a + y*b = n的二元组个数，要求n, a, b, x, y皆为正整数
2方法：先预处理小于n的数的约数，然后暴力试探＋剪枝，试探符合题意的二元组个数，时间复杂度 1/x 从1到n积分，为nln(n)

vjudge题目链接

建议参考博客１
建议参考博客２

以下为Accepted代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 4;
vector <int> y_b[N];
vector <int> :: iterator b;
int book[N];
int main(){
    int n, i, j, a, x, t, ans;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        for(j = 1; j*j <= i; j++){
            if(i%j == 0){
                y_b[i].push_back(j);
                if(i*i != j){
                    t = i / j;
                    y_b[i].push_back(t);
                }
            }
        }
        sort(y_b[i].begin(), y_b[i].end(), greater<int>());
    }
    ans = 0;
    for(a = 1; a < n; a++){
        for(x = 1; x*a < n; x++){
            t = n - x*a;
            for(b = y_b[t].begin(); b != y_b[t].end(); b++){
                if((*b) <= a)
                    break;
                if(book[*b] != a){
                    ans++;
                    book[*b] = a;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

以下为建议参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 4;
vector <int> y_b[N];/*记录当前元素的约数*/
vector <int> :: iterator b;
int book[N];/*实数型全局变量初始化默认为0*/
bool cmp(int a, int b){
    return a > b;
}
int main(){
    int n, i, j, a, x, t, ans;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        for(j = 1; j*j <= i; j++){
            if(i%j == 0){
                y_b[i].push_back(j);
                if(i*i != j){
                    t = i / j;
                    y_b[i].push_back(t);
                }
            }
        }
        sort(y_b[i].begin(), y_b[i].end(), greater<int>());
    }
    ans = 0;
    for(a = 1; a < n; a++){
        for(x = 1; x*a < n; x++){
            t = n - x*a;
            for(b = y_b[t].begin(); b != y_b[t].end(); b++){
                if((*b) <= a)/*题意：a < b*/
                    break;
                if(book[*b] != a){
   /*标记判重*/
                    ans++;
                    book[*b] = a;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}