ICPC-无限路之城（数学+思维）

链接：https://ac.nowcoder.com/acm/contest/321/C

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 131072K，其他语言262144K

64bit IO Format: %lld

题目描述

集训队里,有一位是城市与环境规划学院出身的队员7373!

某一天7373在坐地铁时,对城市的公共交通规划产生了兴趣.

他知道一个有趣的事实:

对于N个点,在任意点之间连接边,只要N-1条边就能让任意两点之间能互相可达

但他现在要规划的可不是普通的城市,是无限路之城

ICPC,InfiniteCreatingPathCity

这个城市中,可以任意在两个地点之间造免费的路!

这些路可以互相交叉,但是每两个地方之间只能造一条边.

现在这个城市中的N个点已经建立了M条边,现在7373想知道,最多还能增加多少条边?

输入描述:

第一行为正整数T,表示测试组数,T<=1000

接下来T组数据,每组一行,包含两个非负整数N,M,其中0<=N<=106,0<=M<=1012

输入数量保证不出现多余的边

输出描述:

T行,每行一个整数,表示最多能增加的边数

示例1

输入

复制

输出

复制

1

1

说明

对于第二组测试数据,

三个点可以恰好形成一个三角形

题解：

每两个点两两相连的总数量为1+2+3.....+m-1。减去已经建立的，就是结果

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

	int T;

	cin>>T;

	long long int a,b;

	for(int t=0;t<T;t++)

	{

		scanf("%lld%lld",&a,&b);

		long long int sum1=a*(a-1)/2;

		long long int sum2=sum1-b;

		printf("%lld\n",sum2);

	}

	return 0;

}

巴特西

ICPC-无限路之城（数学+思维）

题目描述

输入描述:

输出描述:

输入

输出

说明

最新文章

热门文章