ProblemB Bad Treap (數論 Math theorm)

題目大意：

給你一個數 n ，然後生成一顆樹，比 root 小的 node 在左邊，比 root 大的 node 在右邊，規則是 \(y = sin(x)\)

要求是可以生成出一個最高高度的樹，但只能用 n 個點。

分析：

這題跟鬼一樣難，是假程式題，真數學題阿！
我對於這題還是沒有辦法很了解，如果看不懂我的可以建議多看別人的 Blog。

P.S. 我也是看他的 Blog

我們的目的就是 n = 最高長度，然後我們在簡化一點題目就是單調隊列最大化。即 root 都是 left or right 有 node。

由於 sin 的週期是 \( 2 \pi \)，但是 \(sin(0) = sin(\pi) \) 會造成一個現象就是有兩個 \(y = sin(x) \)，所以我們必須再將範圍縮小至 \( \dfrac{-2}{\pi} \sim \dfrac{2}{\pi} \)。
但因為 sin 的週期很難控制，也抓不太到規律。
於是我們現在有了一個新的任務，找出最小點，透過倍數來完成這題。
但是 sin 的倍數不會調整嗎? 會，但是我們只要找出最小點，這個最小點再乘以 50000 倍也不超過 \( \dfrac{-2}{\pi} \sim \dfrac{2}{\pi} \)，這樣就可以了！
接下來要怎麼找呢? 這裡就很神奇瞜!

由於太神奇了，我特別拉出來講，我們要找出一個極小值，我們就先假設 0.0035 ，當 sin (0.0035 角度) = 0.00006，夠我們使用了。怎麼說呢? 因為我們 \( \pi = 3.14 \)，然後我們需要 50000 個數值，所以 \( \dfrac{-2}{\pi} = -25000 * 0.00006 \) and \( \dfrac{2}{\pi} = 0.00006 * 25000 \) 且因 \(25000 + 25000 = 50000 \)，就能搞定題目的 50000 個數值了！最後我們剩下一個任務就能把解題的必要元素都解出來。
P.S. 不一定要用 0.0035 ，只要能夠找出一個可以在 \( \dfrac{-2}{\pi} \sim \dfrac{2}{\pi} \) 能放入 50000個等比級數即可，我有考慮使用過 sin(0.002 角度) = 0.00003，但我解不出下方公式 A , B

公式如下:
\( sin(A * 360 + 0.0035)度數 = sin(B) 弧度\) and \( A , B \in Z \)
Z 則是我們需要的答案。

由於題目說過 B 必須為整數，A 則是由於 sin 週期而必須是整數。
這時候呢，這條公式我則是透過看解答解開的， A = 113 , B = 710，我想不出有甚麼公式或是可以寫一個簡單的程式可以順利找出來。如果知道還請聯絡我，拜託了QQ
P.S. 我覺得只能透過暴力解，才能解出。

接下來就是看他有幾個數列就直接乘以 B 即可，但還需要減去 25000 * B，因為我們是從 \( \dfrac{-2}{\pi} \) 開始。

作者心得

這題也太難了吧，俄羅斯人都跟鬼一樣強阿，此題考的不是寫出來的程式，而是你需要非常清晰的邏輯與能夠解出公式的 A 與 B，若是你能解出來，你的實力肯定在我之上，我佩服你！
(然後解出來，就告訴我你的想法吧！)

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define ll long long
using namespace std;


int main(){
    int n ;
    cin >> n ;
    for(ll i = 0 ; i < n ; i++)
        cout << i * 710 - 25000 * 710 << '\n' ;
    return 0;
}