http://acm.hust.edu.cn/vjudge/contest/view.action?cid=34912#problem/A
解法:
枚举k,二分n
关键点:
1.枚举时候只考虑n - k >= k的情况,另一半由对称性得到
2.大数求组合数时,注意处理超范围的情况
细节处理:
1.对于C(2k' - 1, k'), n - k = k' - 1 < k' 所以枚举的时候对于一个k,n >= 2k
2.给定一个k值,那么C(2k, k)是最小值,如果最小值大于给定的值,那么结束枚举.可以发现,C(2k, k)增长的速度很快,所以枚举很快就能结束
3.二分n求组合数时,先一直乘,如果大于long long的最大值,那么除
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <fstream>
using namespace std;
//LOOP
#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
//OTHER
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define all(x) (x).begin(),(x).end()
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d\n", n)
#define WS(n) printf("%s\n", n)
//debug
//#define online_judge
#ifndef online_judge
#define debugt(a) cout << (#a) << "=" << a << " ";
#define debugI(a) debugt(a) cout << endl
#define debugII(a, b) debugt(a) debugt(b) cout << endl
#define debugIII(a, b, c) debugt(a) debugt(b) debugt(c) cout << endl
#define debugIV(a, b, c, d) debugt(a) debugt(b) debugt(c) debugt(d) cout << endl
#else
#define debugI(v)
#define debugII(a, b)
#define debugIII(a, b, c)
#define debugIV(a, b, c, d)
#endif
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> VI;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;
const int MOD = 100000007;
const int MAXN = 1000010;
const double PI = acos(-1.0);
const LL LL_MAX = (~(unsigned long long)0) >> 1;
const LL MAX = (LL)1e15 + 100;
const int MAX_INDEX = 1001;
LL f[MAX_INDEX][MAX_INDEX];
LL ipt;
typedef pair<LL, LL> PLL;
vector<PLL> v;
#define MP make_pair
LL C(LL a, LL b)
{
LL ret = 1, ta = a - b + 1, tb = 1;
while (ta <= a && tb <= b)
{
if (ret > LL_MAX / a)
ret /= tb++;
else
ret *= a--;
}
if (ta > a)
while (tb <= b) ret /= tb++;
else
return ipt + 1;
return ret;
}
LL bse(LL l, LL r, LL k)
{
LL m;
while (l <= r)
{
m = (l + r) >> 1;
if (C(m, k) <= ipt) l = m + 1;
else r = m - 1;
}
return r;
}
void fun(LL n)
{
int k = 2;
while (C(2 * k, k) <= ipt)
{
LL t = bse(2 * k, 1000000000, k);
if (C(t, k) == ipt)
{
v.push_back(MP(t, k));
v.push_back(MP(t, t - k));
}
k++;
}
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int kase;
RI(kase);
while (kase--)
{
v.clear();
cin >> ipt;
v.push_back(MP(ipt, 1));
v.push_back(MP(ipt, ipt - 1));
fun(ipt);
sort(v.begin(), v.end());
int size = unique(v.begin(), v.end()) - v.begin();
cout << size << endl;
REP(i, size)
{
if (i != 0) putchar(' ');
cout << '(' << v[i].first << ',' << v[i].second << ')';
}
cout << endl;
}
return 0;
}
分享到:
相关推荐
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
My solution for some spoj problems
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
Online Judge Problem solution VN.SPOJ
教程SPOJ HướngdẫnvàchiasẻlờigiảichocácProblemstrênvn.spoj.com。 发展 确保没有在计算机上安装Ruby sudo apt install ruby ruby-dev 安装jekyll主题或直接键入 gem install bundler jekyll 在gem中...
spoj MSTS kruskal +生成树
spoj_tournament_page 将写一个页面来显示参加SPOJ锦标赛的参与者的排名,该竞赛是由ProPTIT俱乐部进行的。
杨弋SPOJ做题表格
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
spoj reverse 的solution
SPOJ_任务SPOJ的任务
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
8 point fft matlab and simulink.
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
SPOJ-Solutions:SPOJ算法问题的解决方案
cp:一些SPOJ问题的解决方案
分机检查spoj用户的排名。 此扩展名有2个选项: - 在选择的比赛中显示用户排名 - 在选择比赛中最多可比较5个用户第一个在后台运行,并在每隔几分钟内更新,您可以设置自己(并默认为15分钟)。当您单击分机的徽标时...
SPOJ( )上选定问题的解决方案