QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723928#5676. Counting Pythagorean TriplesBackToSquare1AC ✓290ms33588kbC++201.8kb2024-11-08 03:49:362024-11-08 03:49:37

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 03:49:37]
  • 评测
  • 测评结果:AC
  • 用时:290ms
  • 内存:33588kb
  • [2024-11-08 03:49:36]
  • 提交

answer

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
 
typedef pair<ll, ll> pl;
typedef pair<ld,ld> pd;
typedef vector<ll> vl;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
 
#define G(x) ll x; cin >> x;
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define all(a) begin(a), end(a)
#define K first
#define V second
#define OK(i,j) i >= 0 && i < n && j >= 0 && j < m
 
#define NN 2505
#define MM 5005
#define MOD 1000007

ll A[NN], B[NN], C[NN];
set<vector<ll>> seen;

void solve() {

    ll n;
    cin >> n;

    ll u = 1, v;
    ll a, b, c;
    while(u < 1251) {
        v = 1;
        while(v < u) {
            if(v > 1 && gcd(u,v) > 1) {
                v++;
                continue;
            }
            a = min(u*u-v*v,2*u*v);
            b = max(u*u-v*v,2*u*v);
            c = u*u+v*v;

            if(gcd(gcd(a,b),c) > 1) {
                v++;
                continue;
            }

            if(seen.count({a,b,c}) == 0) {
                seen.insert({a,b,c});
                if(a < NN) A[a]++;
                if(b < NN) B[b]++;
                if(c < NN) C[c]++;
            }
            v++;
        }
        u++;
    }

    ll ans[4];
    ans[0] = C[n];
    ans[1] = 0;
    for(ll i=2;i<n;i++) if(n%i == 0) ans[1] += C[i];

    ans[2] = A[n] + B[n];
    ans[3] = 0;
    for(ll i=2;i<n;i++) if(n%i == 0) ans[3] += A[i] + B[i];

    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << ' ' << ans[3] << '\n';

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);

    solve();

    return 0;

}

详细

Test #1:

score: 100
Accepted
time: 290ms
memory: 33372kb

input:

65

output:

2 2 2 2

result:

ok single line: '2 2 2 2'

Test #2:

score: 0
Accepted
time: 259ms
memory: 33360kb

input:

64

output:

0 0 1 4

result:

ok single line: '0 0 1 4'

Test #3:

score: 0
Accepted
time: 265ms
memory: 33292kb

input:

2023

output:

0 2 2 5

result:

ok single line: '0 2 2 5'

Test #4:

score: 0
Accepted
time: 260ms
memory: 33512kb

input:

1560

output:

0 4 8 59

result:

ok single line: '0 4 8 59'

Test #5:

score: 0
Accepted
time: 272ms
memory: 33572kb

input:

1625

output:

2 8 2 8

result:

ok single line: '2 8 2 8'

Test #6:

score: 0
Accepted
time: 272ms
memory: 33292kb

input:

1888

output:

0 0 2 11

result:

ok single line: '0 0 2 11'

Test #7:

score: 0
Accepted
time: 268ms
memory: 33508kb

input:

2125

output:

2 8 2 8

result:

ok single line: '2 8 2 8'

Test #8:

score: 0
Accepted
time: 278ms
memory: 33292kb

input:

1950

output:

0 7 0 22

result:

ok single line: '0 7 0 22'

Test #9:

score: 0
Accepted
time: 254ms
memory: 33312kb

input:

2477

output:

1 0 1 0

result:

ok single line: '1 0 1 0'

Test #10:

score: 0
Accepted
time: 266ms
memory: 33312kb

input:

1728

output:

0 0 2 36

result:

ok single line: '0 0 2 36'

Test #11:

score: 0
Accepted
time: 278ms
memory: 33288kb

input:

2249

output:

2 2 2 2

result:

ok single line: '2 2 2 2'

Test #12:

score: 0
Accepted
time: 260ms
memory: 33284kb

input:

2176

output:

0 1 2 17

result:

ok single line: '0 1 2 17'

Test #13:

score: 0
Accepted
time: 277ms
memory: 33288kb

input:

2467

output:

0 0 1 0

result:

ok single line: '0 0 1 0'

Test #14:

score: 0
Accepted
time: 266ms
memory: 33588kb

input:

1898

output:

0 4 0 4

result:

ok single line: '0 4 0 4'

Test #15:

score: 0
Accepted
time: 256ms
memory: 33292kb

input:

2048

output:

0 0 1 9

result:

ok single line: '0 0 1 9'

Test #16:

score: 0
Accepted
time: 272ms
memory: 33244kb

input:

1875

output:

0 4 2 11

result:

ok single line: '0 4 2 11'

Test #17:

score: 0
Accepted
time: 264ms
memory: 33352kb

input:

2187

output:

0 0 1 6

result:

ok single line: '0 0 1 6'

Test #18:

score: 0
Accepted
time: 267ms
memory: 33380kb

input:

2431

output:

0 4 4 9

result:

ok single line: '0 4 4 9'

Test #19:

score: 0
Accepted
time: 266ms
memory: 33304kb

input:

2028

output:

0 2 4 18

result:

ok single line: '0 2 4 18'

Test #20:

score: 0
Accepted
time: 267ms
memory: 33356kb

input:

1105

output:

4 9 4 9

result:

ok single line: '4 9 4 9'

Test #21:

score: 0
Accepted
time: 266ms
memory: 33244kb

input:

2210

output:

0 13 0 13

result:

ok single line: '0 13 0 13'

Test #22:

score: 0
Accepted
time: 267ms
memory: 33352kb

input:

2465

output:

4 9 4 9

result:

ok single line: '4 9 4 9'

Test #23:

score: 0
Accepted
time: 282ms
memory: 33512kb

input:

2187

output:

0 0 1 6

result:

ok single line: '0 0 1 6'