in c++

Use this C++ solution:

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

long long solution(int N) {
    vector<int> spf(N + 1);
    
    // Smallest prime factor sieve
    for (int i = 0; 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> freq;

    // Compute square-free kernel of every number
    for (int x = 1; x <= N; x++) {
        int t = x;
        int kernel = 1;

        while (t > 1) {
            int p = spf[t];
            int cnt = 0;
            while (t % p == 0) {
                t /= p;
                cnt++;
            }
            if (cnt % 2 == 1) kernel *= p;
        }

        freq[kernel]++;
    }

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

    return ans;
}

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

How it works:

• i * j is a perfect square iff i and j have the same square-free part.
• Example:
  • 12 = 3 * 2^2 → square-free part = 3
  • 27 = 3 * 3^2 → square-free part = 3
  • so 12 * 27 is a perfect square.
• Count how many numbers from 1..N share the same square-free part.
• If a group has size k, it contributes k * k ordered pairs.

For the sample:

• N = 3
• valid pairs: (1,1), (2,2), (3,3)
• answer = 3

Time complexity: O(N log log N) Space complexity: O(N)

If you want, I can also give a more interview-style version with the solution(int N) function only.

sql
SELECT 
    c.name,
    SUM(oi.quantity * oi.price) AS total_spent
FROM customers c
JOIN orders o
    ON c.customer_id = o.customer_id
JOIN order_items oi
    ON o.order_id = oi.order_id
GROUP BY c.customer_id, c.name
HAVING SUM(oi.quantity * oi.price) > 500
ORDER BY total_spent DESC;

For the sample, this returns:

sql
Alice | 600

Because Alice spent:

• Laptop: 1 * 400 = 400
• Mouse: 2 * 50 = 100
• Keyboard: 1 * 100 = 100

Total = 600

If you want, I can also give a PostgreSQL/MSSQL-compatible version, but this one works in MySQL 8.0.