Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- using namespace std;
- const int N = (int)1e6 + 10;
- vector<int> g[N];
- int dp[N];
- int L;
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- for (int v = 2; v * v < N; v++)
- {
- for (int u = 1; u < v; u++)
- {
- int x = v * v - u * u;
- int y = 2 * v * u;
- int z = v * v + u * u;
- for (int k = 1; k * z < N; k++)
- {
- g[x * k].push_back(z * k);
- g[y * k].push_back(z * k);
- }
- }
- }
- for (int x = 1; x < N; x++)
- for (int y : g[x])
- dp[y] = max(dp[y], dp[x] + 1);
- cin >> L;
- cout << dp[L];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement