logoChat01.ai

Square investment Bob and John both have N dollar...

Criado em: 21 de abril de 2026

Respondido usando GPT-5.4 Thinking por Chat01

Pergunta

Square investment

Bob and John both have N dollars each and want to invest some money in Jack. They will invest amounts, j(1 ≤ i, j ≤ N), Jack has promised them a return of * *, Bob and John will be happy if the return is a perfect square.

Il wite poor

11

12

11

cin

14

15

16

out

fout 14

Task

alidanish .com

2026-04-22 01:18 UTC

of investment (2,1) such return is a perfect Calculate the number of pairs of i square.

30-04-22 01

Example 1

Assumptions

Input

N=4

Output: 6

[email protected]

2026-04-22 01:18. UTC

A

2006-04-22

(1, 1), (1, 4), (2, 2), (3, 3), (4, 1), and (4, 4) are the possible pairs.

Function description

Complete the function solution(). The function takes the following parameter and returns the solution:
Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.

alidanish

22 01:18 UTC

20 The first line contains N, denoting the total amount.

106-04-22 07:18C

Output format

Return an integer representing the number of possible pairs.

Constraints

1 ≤ N ≤ 105

Sample Input 1

3

Sample Output 1

3
Note: Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.

2

Limits

23

[→

Time Limit: 1.0 sec(s) for each Input file

@gmail.com

Memory Limit: 256 MB

01:18 UTC

Source Limit: 1024 KR22

Please give m short right code

Pensamento

Thought for 4s

Resposta

Use this idea:

i * j is a perfect square iff i and j have the same square-free part.

So:

  1. For every number x from 1..N, reduce it by removing all square factors.
  2. Count how many numbers give the same reduced value.
  3. If a value appears c times, it contributes c*c pairs (i,j).

Short C++ code

cpp
#include <bits/stdc++.h>
using namespace std;

long long solution(int N) {
    vector<int> spf(N + 1);
    for (int i = 1; i <= N; i++) spf[i] = i;
    for (int i = 2; i * i <= N; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j <= N; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }

    unordered_map<int, long long> cnt;

    for (int x = 1; x <= N; x++) {
        int y = x, k = 1;
        while (y > 1) {
            int p = spf[y], c = 0;
            while (y % p == 0) y /= p, c++;
            if (c % 2) k *= p;
        }
        cnt[k]++;
    }

    long long ans = 0;
    for (auto &it : cnt) ans += it.second * it.second;
    return ans;
}

int main() {
    int N;
    cin >> N;
    cout << solution(N);
    return 0;
}

Example

For N = 4, output is:

cpp
6

If you want, I can also give an even smaller version.

Pergunta

#include<bits/stdc++.

1>

// Write your code here

3 int solution (int N) {

4

5

6789

return 0;

C

10

7v}

int main() {

I

11

12

9

ios::sync_with_stdio(0);

13

cin.tie(0);

int N;

14

cin >> N;

15

16

int out;

17

out = solution(N);

18

19 }
According this code

Pensamento

Thought for a few seconds

Resposta

Use this in your format:

cpp
#include <bits/stdc++.h>
using namespace std;

// Write your code here
int solution(int N) {
    vector<int> cnt(N + 1, 0);

    for (int x = 1; x <= N; x++) {
        int y = x, k = 1;
        for (int p = 2; p * p <= y; p++) {
            int c = 0;
            while (y % p == 0) {
                y /= p;
                c++;
            }
            if (c % 2) k *= p;
        }
        if (y > 1) k *= y;
        cnt[k]++;
    }

    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += 1LL * cnt[i] * cnt[i];
    }

    return (int)ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int out;
    out = solution(N);
    cout << out;

    return 0;
}

For input:

cpp
3

Output:

cpp
3

Compartilhar esta Q&A