結果

問題 No.2119 一般化百五減算
コンテスト
ユーザー kotatsugame
提出日時 2022-11-04 21:42:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 1,096 bytes
コンパイル時間 766 ms
コンパイル使用メモリ 78,540 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 19:25:00
合計ジャッジ時間 1,921 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N,M;
int val[1<<17];
bool isp[1<<17];
main()
{
	cin>>N>>M;
	for(int i=1;i<=1e5;i++)val[i]=-1;
	for(int i=0;i<M;i++)
	{
		int B,C;cin>>B>>C;
		C=(C%B+B)%B;
		if(val[B]==-1)val[B]=C;
		else if(val[B]!=C)
		{
			cout<<"NaN"<<endl;
			return 0;
		}
	}
	vector<pair<int,int> >Q;
	int mv=0;
	for(int p=2;p<=1e5;p++)if(!isp[p])
	{
		for(int i=p+p;i<=1e5;i+=p)isp[i]=true;
		vector<pair<int,int> >x;
		for(int i=p;i<=1e5;i+=p)if(val[i]!=-1)
		{
			int u=i,t=1;
			while(u%p==0)
			{
				u/=p;
				t*=p;
			}
			x.push_back(make_pair(t,val[i]%t));
		}
		if(!x.empty())
		{
			sort(x.begin(),x.end());
			int C=x.back().second,B=x.back().first;
			for(pair<int,int>p:x)
			{
				if(C%p.first!=p.second)
				{
					cout<<"NaN"<<endl;
					return 0;
				}
			}
			Q.push_back(make_pair(C,B));
			mv=max(mv,C);
		}
	}
	for(int n=mv;n<=N;n++)
	{
		bool ok=true;
		for(pair<int,int>p:Q)
		{
			if(n%p.second!=p.first)
			{
				ok=false;
				break;
			}
		}
		if(ok)
		{
			cout<<n<<endl;
			return 0;
		}
	}
	cout<<"NaN"<<endl;
}
0