【TP SRM 703 div2 500】 GCDGraph
Problem Statement
You are given four ints: n, k, x, and y. The ints n and k describe a simple undirected graph. The graph has n nodes, numbered 1 through n. Two distinct vertices i and j are connected by an edge if and only if gcd(i, j) > k. Here, gcd(i, j) denotes the greatest common divisor of i and j. The ints x and y are the numbers of two (not necessarily distinct) vertices in our graph. Return “Possible” if it is possible to travel from x to y by following the edges of our graph. Otherwise, return “Impossible”. In other words, return “Possible” if our graph contains a path that connects the nodes x and y, and “Impossible” if there is no such path.
Definition
Class:
GCDGraph
Method:
possible
Parameters:
int, int, int, int
Returns:
string
Method signature:
string possible(int n, int k, int x, int y)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
256
Stack limit (MB):
256
Constraints
n will be between 2 and 1,000,000, inclusive.
k will be between 0 and n, inclusive.
x and y will be between 1 and n, inclusive.
Examples
0)
12
2
8
9
Returns: “Possible”
We have a graph with n = 12 nodes. As k = 2, vertices i and j are connected by an edge if and only if gcd(i, j) is strictly greater than 2. In this graph it is possible to travel from node 8 to node 9. One possible path: 8 -> 4 -> 12 -> 9.
1)
12
2
11
12
Returns: “Impossible”
This is the same graph as in Example 0, but now we are interested in another pair of nodes. It is not possible to travel from node 11 to node 12. In particular, in our graph node 11 is an isolated node because for any other node x we have gcd(11, x) = 1.
2)
12
2
11
11
Returns: “Possible”
A node is always reachable from itself.
3)
10
2
8
9
Returns: “Impossible”
4)
1000000
1000
12345
54321
Returns: “Possible”
5)
1000000
2000
12345
54321
Returns: “Impossible”
6)
2
0
1
2
Returns: “Possible”
【题目链接】:
【题解】
大意是说两个节点之间有边当且仅当两个节点的标号的gcd>k;
可以这样.
先枚举比k大的且比n小的数i;
然后它的倍数和它之间连了一条边.
表示这两个数的最大公因数为i;而i大于k;所以满足题意;
而所有i的出度点之间则肯定也有路径可以到达了。
可以这样想?
两个数x,y的gcd为i
则i和y的gcd为i
i和x的gcd也为i
即x和y肯定是i的倍数.
所以如果i大于k
这对关系x,y肯定能找出来;(用并查集判断就可以了);
其他的要通过间接关系找出来的也同理吧!
用并查集描述两个数之间是否联通即可.
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 1e6+100;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const double pi = acos(-1.0);
int f[MAXN];
int ff(int x)
{
if (f[x]!=x)
f[x] = ff(f[x]);
else
return x;
return f[x];
}
class GCDGraph
{
public:
string possible(int n, int k, int x, int y)
{
rep1(i,1,n)
f[i] = i;
rep1(i,k+1,n)
{
int fa = ff(i);
for (int j = 2*i;j <= n;j+=i)
{
int r1 = ff(j);
f[r1] = fa;
}
}
if (ff(x)==ff(y))
return "Possible";
else
return "Impossible";
}
};
最新文章
- MVC、MVP、MVVM、Angular.js、Knockout.js、Backbone.js、React.js、Ember.js、Avalon.js、Vue.js 概念摘录
- poj3122-Pie(二分法+贪心思想)
- MongoDB学习笔记七:管理
- Autofac的高级使用——Autofac.2.6.3.862
- Java NIO之通道Channel
- C# ASP.NET MVC HtmlHelper用法大全
- double函数和int函数
- 【原】《Git教程》学习笔记
- Java之MySql数据库链接
- [zz] 使用ssh公钥密钥自动登陆linux服务器
- js运动
- 小编接地气——第六届中国云计算大会攻略Q&;amp;A
- debug(fmt,args...)调试
- Unicode的解救方案 - Windows程序设计(SDK)002
- pca图像识别
- ERP报错:所在的期间无效,但又无法新增账套期间。
- mySQL语法中的存储过程及if语句的使用简例
- java后台验证码工具
- PostgreSql扩展Sql-动态加载共享库(C函数)
- 数据库主库从库宕机重启后binlog数据同步