ural1682 Crazy Professor
2024-10-16 06:46:46
Crazy Professor
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Professor Nathan Mathan is crazy about mathematics. For an unknown reason, he started to write on the blackboard all positive integers starting from 1. After writing a new number a, Professor draws lines connecting it with all the numbers b that are already on the blackboard and satisfy at least one of the conditions:
- b + a · a ≡ 0 (mod k),
- a + b · b ≡ 0 (mod k),
where k is some parameter.
Nobody can persuade him to stop this meaningless procedure. Professor says that he will stop as soon as there appears a cycle in the graph of the numbers on the blackboard. But only Professor knows when that will happen and whether it will happen at all. Help his colleagues determine after which number he will stop.
Input
You are given the integer k (1 ≤ k ≤ 100000).
Output
Output the number after which the first cycle will appear in the graph. If it never happens, output −1.
Sample
input | output |
---|---|
2 |
5 |
Notes
In example after Professor had written all integers from 1 to 4 the graph contained edges (1, 3) and (2, 4). After writing number 5, Professor connects it with numbers 1 and 3, so the cycle 1-5-3-1 appears in the graph.
分析:并查集+同余定理;
注意可能有两条重边,要排除;
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=2e5+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
int n,m,k,t,p[maxn],now[maxn];
vi mo[maxn];
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
int main()
{
int i,j;
scanf("%d",&k);
rep(i,,maxn-)p[i]=i;
for(i=;;i++)
{
ll q=((ll)i*i/k+)*k;
while((j=q-(ll)i*i)<i)
{
int x=find(j),y=find(i);
if(x==y)return *printf("%d\n",i);
else p[x]=y;
now[j]=i;
q+=k;
}
q=(ll)(i/k+)*k;
for(int x:mo[(q-i)%k])
{
if(now[x]==i)continue;
int y=find(x),r=find(i);
if(y==r)return *printf("%d\n",i);
else p[y]=r;
}
mo[(ll)i*i%k].pb(i);
}
//system("Pause");
return ;
}
最新文章
- HBase基本shell命令
- 北京电子科技学院(BESTI)实验报告5
- 自己练习读取写入txt
- 分布式HBase-0.98.4环境搭建
- C# 利用BarcodeLib.dll生成条形码(一维,zxing,QrCodeNet/dll二维码)
- codeforces 652B z-sort(思维)
- storyBoard中的Segue跳转
- Cocos2d-x学习笔记(六) 定时器Schedule的简单应用
- RabbitMQ基本管理(上)
- sourcestress 问题解决方案
- 计算机网络相关:应用层协议(一):DNS
- 常用的前端相关chrome插件
- docker环境下的测试
- scipy.stats
- mysql++ 3.2.3 源码安装
- .Net编译原理简单介绍
- 家庭房产L2-007
- charles使用教程 干货~
- Docker Macvlan
- arcgis新版本增加的功能