fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <numeric>
  5.  
  6. using namespace std;
  7.  
  8. const int MAX_N = 1000000;
  9.  
  10. // Cấu trúc lưu một điểm tọa độ nguyên
  11. struct Point {
  12.     long long x, y;
  13. };
  14.  
  15. // Hàm tính giá trị tuyệt đối |x| + |y|
  16. long long manhattan_dist(long long x, long long y) {
  17.     return abs(x) + abs(y);
  18. }
  19.  
  20. // Tổng đáp án
  21. long long total_S = 0;
  22.  
  23. // Hàm xử lý khi có một bộ ba Pytago (a, b, c) với c là mẫu số
  24. void process_pythagorean_triple(long long a, long long b, long long c) {
  25.     // Trong thực tế của Problem 450, bạn sẽ không duyệt R, r trực tiếp
  26.     // mà sẽ dùng 'c' (và các lũy thừa của c) để tính toán số lượng 
  27.     // các cặp (R, r) là bội số hợp lệ của c.
  28.  
  29.     // Ví dụ cơ bản (Minh họa logic đại số hóa):
  30.     // r phải chứa nhân tử của c^K, với K liên quan đến (R-r)/r.
  31.     // Thay vì duyệt, ta cộng dồn số cách chọn R, r thông qua các hàm 
  32.     // toán học đếm số bội số (Multiples Counting) trong giới hạn N.
  33.  
  34.     /* long long multiples_count = count_valid_pairs(c, MAX_N);
  35.     total_S += multiples_count * ...; 
  36.     */
  37. }
  38.  
  39. // Sinh các bộ ba Pytago nguyên thủy bằng thuật toán Berggren (Tree of PPTs)
  40. // a, b là 2 cạnh góc vuông, c là cạnh huyền (mẫu số của sin(t), cos(t))
  41. void generate_PPT(long long a, long long b, long long c) {
  42.     // Điều kiện dừng: nếu mẫu số c vượt quá một giới hạn liên quan tới N
  43.     // (Lưu ý: Giới hạn thực tế của c phụ thuộc vào phân tích Diophantine của R, r)
  44.     if (c > MAX_N) return;
  45.  
  46.     process_pythagorean_triple(a, b, c);
  47.  
  48.     // 3 ma trận sinh nhánh cho cây Pytago
  49.     long long a1 =  a - 2*b + 2*c;
  50.     long long b1 =  2*a - b + 2*c;
  51.     long long c1 =  2*a - 2*b + 3*c;
  52.     generate_PPT(a1, b1, c1);
  53.  
  54.     long long a2 =  a + 2*b + 2*c;
  55.     long long b2 =  2*a + b + 2*c;
  56.     long long c2 =  2*a + 2*b + 3*c;
  57.     generate_PPT(a2, b2, c2);
  58.  
  59.     long long a3 = -a + 2*b + 2*c;
  60.     long long b3 = -2*a + b + 2*c;
  61.     long long c3 = -2*a + 2*b + 3*c;
  62.     generate_PPT(a3, b3, c3);
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(NULL);
  68.  
  69.     cout << "Bat dau tinh toan T(10^6)..." << "\n";
  70.  
  71.     // Khởi tạo từ bộ ba Pytago nguyên thủy nhỏ nhất (3, 4, 5)
  72.     // Các góc thoả mãn sin(t), cos(t) hữu tỉ (ngoại trừ các góc phần tư 0, 90, 180, 270)
  73.     // đều được sinh ra từ đây.
  74.     generate_PPT(3, 4, 5);
  75.  
  76.     // Xử lý riêng biệt các góc suy biến (degenerate angles) 
  77.     // tương ứng với c = 1 (tức là t = 0, pi/2, pi, 3pi/2)
  78.     // Ở các góc này, điểm sinh ra luôn là số nguyên với mọi R, r.
  79.     // Việc của ta là dùng công thức cấp số cộng để tính tổng S(R, r) cho c = 1.
  80.     /*
  81.     for (long long R = 3; R <= MAX_N; ++R) {
  82.         long long max_r = (R - 1) / 2;
  83.         // Tính tổng tọa độ bằng công thức O(1) thay vì duyệt r
  84.         total_S += calculate_degenerate_sum(R, max_r); 
  85.     }
  86.     */
  87.  
  88.     cout << "T(10^6) = " << total_S << "\n";
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Bat dau tinh toan T(10^6)...
T(10^6) = 0
https://ideone.com/GUuK7k
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!