[Question] Dart

By Game

Title description

Xiao Ming likes to play darts, and he will record each score in an array. Today there is a dart grand prize. The rules for winning the prize are: if you score 4 darts in sequence (a, b, c, d), satisfy a×b×c=d.

Xiao Ming is going to delete the other items in the record, leaving only 4 scores that meet the criteria for the award. He would like to ask how many different solutions do you have?

Input and output format

Input format

The first line, an integer N. (N <= 2000)

The second line, N integers, each integer ranges in [1…106< /mn>

“>10^6].

Output format

One line, an integer, representing the number of solutions.

Input and output sample

< strong>Input example one

6

10 2 2 7 40 160

Output sample one

2

< div class="col-xs-12">

Input example two

8

< p>128 64 32 16 8 4 2 1

Output sample two

0

Problem solution

Violent enumeration a, b, c, ask whether d exists, you can do O( n³) time complexity, but obviously cannot meet the data range of this question.

We can start from another angle. From the question a*b=d/c, we can first enumerate a*b, record the position where b appears, then enumerate d/c, and find the number of cases that satisfy the position of b according to the position of c. This seems to be O(n³), but in fact, using binary search optimization can achieve O(n²logn), which happens to pass this question.

share picture 

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 2; i + 2 <= n; ++i)

 {

 for(register int j = 1; j j)

 {

 if((long long)a[i] * a[j]> PTS) continue;

 c[a[i] * a[j]].push_back(i);

}

}

 for(register int i = 3; i i)

 {

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += BS(a[j] / a[i], i);

 // cout << i << "" << j < <"" << ans << endl;

}

}

 cout << ans;

 return 0;

}

Reference program O(n²logn) version

However, when the data range is enlarged again In some cases, the above approach will not work. We can look at the shortcomings of the above approach, which lies in the need to find the position of b. If we can enumerate a*b at the same time when enumerating d/c, we can achieve O(n²) time complexity, and this It can be achieved, just use the feature that the position of b is in front of the position of c. For details, please refer to the following program. (And this method is better to write..)

share picture 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 3; i i)

 {

 for(register int j = 1; j 1; ++ j)

 {

 if((long long)a[i-1] * a[j]> PTS) continue;

 ++c[a[i-1] * a[j ]];

}

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += c[a[j] / a[i]];

}

}

 cout << ans;

 return 0;

}

reference program O(n²) version

Input example one

6

10 2 2 7 40 160

Output sample one

2

Input example one

6

< p>10 2 2 7 40 160

Output sample one

2

Input example two

8

128 64 32 16 8 4 2 1

Output sample Example 2

0

Problem solution

Violent enumeration a, b, c, ask whether d exists, The time complexity of O(n³) can be achieved, but obviously it cannot meet the data range of this question.

We can start from another angle. From the question a*b=d/c, we can first enumerate a*b, record the position where b appears, then enumerate d/c, and find the number of cases that satisfy the position of b according to the position of c. This seems to be O(n³), but in fact, using binary search optimization can achieve O(n²logn), which happens to pass this question.

share picture 

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 2; i + 2 <= n; ++i)

 {

 for(register int j = 1; j j)

 {

 if((long long)a[i] * a[j]> PTS) continue;

 c[a[i] * a[j]].push_back(i);

}

}

 for(register int i = 3; i i)

 {

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += BS(a[j] / a[i], i);

 // cout << i << "" << j < <"" << ans << endl;

}

}

 cout << ans;

 return 0;

}

Reference program O(n²logn) version

However, when the data range is enlarged again In some cases, the above approach will not work. We can look at the shortcomings of the above approach, which lies in the need to find the position of b. If we can enumerate a*b at the same time when enumerating d/c, we can achieve O(n²) time complexity, and this It can be achieved, just use the feature that the position of b is in front of the position of c. For details, please refer to the following program. (And this method is better to write..)

share picture 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 3; i i)

 {

 for(register int j = 1; j 1; ++ j)

 {

 if((long long)a[i-1] * a[j]> PTS) continue;

 ++c[a[i-1] * a[j ]];

}

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += c[a[j] / a[i]];

}

}

 cout << ans;

 return 0;

}

reference program O(n²) version

Input example two

8

128 64 32 16 8 4 2 1

< /p>

Sample output 2

0

Problem solution

Violent enumeration of a, b, c and finding whether d exists can achieve O(n³) time complexity, but obviously it does not satisfy the data range of this question.

We can start from another angle. From the question a*b=d/c, we can first enumerate a*b, record the position where b appears, then enumerate d/c, and find the number of cases that satisfy the position of b according to the position of c. This seems to be O(n³), but in fact, using binary search optimization can achieve O(n²logn), which happens to pass this question.

share picture 

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 2; i + 2 <= n; ++i)

 {

 for(register int j = 1; j j)

 {

 if((long long)a[i] * a[j]> PTS) continue;

 c[a[i] * a[j]].push_back(i);

}

}

 for(register int i = 3; i i)

 {

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += BS(a[j] / a[i], i);

 // cout << i << "" << j < <"" << ans << endl;

}

}

 cout << ans;

 return 0;

}

Reference program O(n²logn) version

However, when the data range is enlarged again In some cases, the above approach will not work. We can look at the shortcomings of the above approach, which lies in the need to find the position of b. If we can enumerate a*b at the same time when enumerating d/c, we can achieve O(n²) time complexity, and this It can be achieved, just use the feature that the position of b is in front of the position of c. For details, please refer to the following program. (And this method is better to write..)

share picture 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

 cin >> n;

 for(register int i = 1; i <= n; ++i)

 {

 cin >> a[i];

}

 for(register int i = 3; i i)

 {

 for(register int j = 1; j 1; ++ j)

 {

 if((long long)a[i-1] * a[j]> PTS) continue;

 ++c[a[i-1] * a[j ]];

}

 for(register int j = i + 1; j <= n; ++j)

 {

 if(a[j]% a[i]) continue< /span>;

 ans += c[a[j] / a[i]];

}

}

 cout << ans;

 return 0;

}

reference program O(n²) version

Share picture 

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1< span style="color: #000000;">];

long long ans;



inline int BS(int x, int p)

{

 int len = c[x].size();

 int lt = 0, rt = len-< span style="color: #800080;">1, mid;

 while(lt <= rt)

 {

 mid = lt + rt >> 1;

 if(c[x][mid] >= p) rt = mid-1;

 else if(mid + 1 1] 1;

 else return mid + 1;

}

 return 0;

}



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 2; i + 2 <= n; ++i)

 {

        for(register int j = 1; j < i; ++j)

 {

            if((long long)a[i] * a[j] > PTS) continue;

            c[a[i] * a[j]].push_back(i);

}

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += BS(a[j] / a[i], i);

            // cout << i << " " << j << " " << ans << endl;

        }

}

    cout << ans;

 return 0;

}

参考程序O(n²logn)版

#include 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

vector<int> c[PTS | 1];

long long ans;



inline int BS(int x, int p)

{

    int len = c[x].size();

    int lt = 0, rt = len - 1, mid;

    while(lt <= rt)

 {

        mid = lt + rt >> 1;

        if(c[x][mid] >= p) rt = mid - 1;

        else if(mid + 1 < len && c[x][mid + 1] < p) lt = mid + 1;

        else return mid + 1;

}

 return 0;

}



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 2; i + 2 <= n; ++i)

 {

        for(register int j = 1; j < i; ++j)

 {

            if((long long)a[i] * a[j] > PTS) continue;

            c[a[i] * a[j]].push_back(i);

}

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += BS(a[j] / a[i], i);

            // cout << i << " " << j << " " << ans << endl;

        }

}

    cout << ans;

 return 0;

}

分享图片 

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = 1; j < i - 1; ++j)

 {

            if((long long)a[i - 1] * a[j] > PTS) continue;

            ++c[a[i - 1] * a[j]];

}

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += c[a[j] / a[i]];

}

}

    cout << ans;

 return 0;

}

参考程序O(n²)版

#include 



#define MAX_N 2000

#define PTS 1000000



using namespace std;



int n;

int a[MAX_N | 1];

int c[PTS | 1];

long long ans;



int main()

{

    cin >> n;

    for(register int i = 1; i <= n; ++i)

 {

        cin >> a[i];

}

    for(register int i = 3; i < n; ++i)

 {

        for(register int j = 1; j < i - 1; ++j)

 {

            if((long long)a[i - 1] * a[j] > PTS) continue;

            ++c[a[i - 1] * a[j]];

}

        for(register int j = i + 1; j <= n; ++j)

 {

            if(a[j] % a[i]) continue;

            ans += c[a[j] / a[i]];

}

}

    cout << ans;

 return 0;

}

,

WordPress database error: [Table 'yf99682.wp_s6mz6tyggq_comments' doesn't exist]
SELECT SQL_CALC_FOUND_ROWS wp_s6mz6tyggq_comments.comment_ID FROM wp_s6mz6tyggq_comments WHERE ( comment_approved = '1' ) AND comment_post_ID = 1736 ORDER BY wp_s6mz6tyggq_comments.comment_date_gmt ASC, wp_s6mz6tyggq_comments.comment_ID ASC

Leave a Comment

Your email address will not be published.