1 条题解
-
0
C++ :
#include <cstdio> #include <cmath> #include <algorithm> typedef unsigned long long u64; /* 设参赛队数 t = 2^k * m(m 为奇数)。淘汰赛共打 m(2^k - 1) 场; 若 m > 1 则剩下的 m 支队进行循环赛,再打 m(m-1)/2 场。 于是 n = m(2^k - 1) + [m>1] * m(m-1)/2 枚举 k,解关于 m 的二次方程 m^2 + (2^d - 3)m - 2n = 0(d = 2^k)。 B 最大约 6.7e17,B^2 会溢出,故用 long double 求根后再用 ULL 精确验证。 */ static u64 res[300]; int main(){ u64 n; if(scanf("%llu",&n)!=1) return 0; int rc=0; for(int k=0;k<64;k++){ u64 A = (k==0)?0ULL:((1ULL<<k)-1ULL); if(A>n) break; if(k>=1 && n==A) res[rc++] = (1ULL<<k); // m = 1 long double B = 2.0L*(long double)A - 1.0L; long double disc = B*B + 8.0L*(long double)n; long double sq = sqrtl(disc); long long cand = (long long)((sq - B)/2.0L); for(long long m=cand-2; m<=cand+2; m++){ if(m<3 || (m%2)==0) continue; u64 M=(u64)m; u64 t1 = M*((M-1)/2); // m(m-1)/2 u64 t2 = M*A; if(t1+t2==n) res[rc++] = (1ULL<<k)*M; } } if(rc==0){ printf("-1\n"); return 0; } std::sort(res,res+rc); int u=0; for(int i=0;i<rc;i++) if(i==0||res[i]!=res[i-1]) res[u++]=res[i]; for(int i=0;i<u;i++) printf("%llu\n", res[i]); return 0; }
- 1
信息
- ID
- 2569
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者