Advertisement
Guest User

Untitled

a guest
Jun 13th, 2015
544
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. const int N = (int)1e6 + 10;
  8. vector<int> g[N];
  9. int dp[N];
  10. int L;
  11.  
  12. int main()
  13. {
  14.     freopen("input.txt", "r", stdin);
  15.     freopen("output.txt", "w", stdout);
  16.  
  17.     for (int v = 2; v * v < N; v++)
  18.     {
  19.         for (int u = 1; u < v; u++)
  20.         {
  21.             int x = v * v - u * u;
  22.             int y = 2 * v * u;
  23.             int z = v * v + u * u;
  24.             for (int k = 1; k * z < N; k++)
  25.             {
  26.                 g[x * k].push_back(z * k);
  27.                 g[y * k].push_back(z * k);
  28.             }
  29.         }
  30.     }
  31.     for (int x = 1; x < N; x++)
  32.         for (int y : g[x])
  33.             dp[y] = max(dp[y], dp[x] + 1);
  34.     cin >> L;
  35.     cout << dp[L];
  36.  
  37.     return 0;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement