C++(g++ 7.5.0) 解法, 执行用时: 368ms, 内存消耗: 2960K, 提交时间: 2022-10-14 17:16:26

#include <bits/stdc++.h>
using namespace std;
typedef long double db;
typedef long long ll;
const db pi=acosl(-1.0);
struct vir {
	db r, i;
	inline vir(db r_=0, db i_=0):r(r_), i(i_) {}
	inline vir& operator += (const vir &rhs) { r+=rhs.r; i+=rhs.i; return *this; }
	inline vir& operator -= (const vir &rhs) { r-=rhs.r; i-=rhs.i; return *this; }
	inline vir& operator *= (const vir &rhs) {
		db rr=r*rhs.r-i*rhs.i;
		db ii=r*rhs.i+i*rhs.r;
		r=rr; i=ii;
		return *this;
	}
	inline vir operator + (const vir &rhs) const { vir lhs=*this; return lhs+=rhs; }
	inline vir operator - (const vir &rhs) const { vir lhs=*this; return lhs-=rhs; }
	inline vir operator * (const vir &rhs) const { vir lhs=*this; return lhs*=rhs; }
	
	inline vir operator ! () const { return vir(r, -i); }
	inline db norm() const { return r*r+i*i; }
	inline vir operator / (const vir &rhs) const {
		vir res=(*this)*(!rhs);
		db len=rhs.norm();
		return vir(res.r/len, res.i/len);
	}
};
ll n, k;
inline ll get_t(ll lim) {
	ll l=0, r=n, mid, res=0;
	while(l<=r) {
		mid=(l+r)/2;
		if((__int128_t)mid*(mid+1)/2<=lim) {
			res=mid;
			l=mid+1;
		}
		else {
			r=mid-1;
		}
	}
	return res;
}
inline vir w(ll n) {
	n%=k;
	db a=2*pi*n/k;
	return vir(cosl(a), sinl(a));
}
inline db ans() {
	cin>>n>>k;
	int r=k/2;
	ll t=get_t(n/r);
	vir res=(vir(1, 0)-w(t*r))/(vir(1, 0)-w(r))-vir(t, 0)*w(t*r);
	res=res/(vir(1, 0)-w(1));
	n-=t*(t+1)/2*r;
	
	res+=vir(t+1, 0)*(w(t*r)-w(n/(t+1)+t*r))/(vir(1, 0)-w(1));

	ll id=n/(t+1)+t*r;
	n%=t+1;
	res+=vir(n, 0)*w(id);
	
	return res.r+res.i;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout<<fixed<<setprecision(12);
	int t; cin>>t;
	while(t--)
		cout<<ans()<<"\n";
	cout.flush();
	return 0;
}

C++ 解法, 执行用时: 495ms, 内存消耗: 3832K, 提交时间: 2022-07-03 14:39:57

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const ld PI = acos(-1);
using c = complex<ld>;

c power(c a, ll b, c res = 1) {
  for (; b; b /= 2, (a *= a))
    if (b & 1) (res *= a);
  return res;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int T;
  cin >> T;
  while (T--) {
    ll n, k, d;
    cin >> n >> k, d = k / 2;
    auto w = c(cos(2 * PI / k), sin(2 * PI / k));
    auto s = [&] {
      ll l = 0, r = n;
      while (l < r) {
        ll mid = (l + r + 1) / 2;
        if (__int128(mid + 1) * mid / 2 <= n / d) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      return r;
    }();
    auto A = (power(w, s * d) - c(1)) / (power(w, d) - c(1)) - c(s) * power(w, s * d);
    A /= (c(1) - w);
    n -= d * (s + 1) * s / 2;
    ll t = n / (s + 1), remain = n % (s + 1);
    auto B = c(s + 1) * power(w, s * d) * ((power(w, t) - c(1)) / (w - c(1)));
    auto C = c(remain) * power(w, s * d + t);
    auto res = A + B + C;
    // cout << res.real() << " " << res.imag() << "\n";
    cout << res.real() + res.imag() << "\n";
  }
}