CometOJ10C 鱼跃龙门

problem

实际上就是对于给定的\(n\)求一个最小的\(x\)满足\(\frac{x(x+1)}{2}=kn(k\in N^*)\)。

solution

对上面的式子稍微变形可得\(x(x+1)=2kn\)。因为\(x\)与\((x+1)\)互质，所以将\(n\)质因数分解后，同种质因子肯定都位于\(x\)或\((x+1)\)中。\(10^{12}\)以内的整数质因数分解后种类不超过\(13\)种，所以可以暴力枚举每种质因子属于\(x\)还是\(x+1\)。

然后分别得到\(a\)和\(b\)。下面要使得\(bx=ay+1\)。扩展欧几里得求解即可。

本题时限\(0.5s\),每次询问都\(\sqrt{n}\)质因数分解是会\(TLE\)的。所以先预处理质数。然后进行质因数分解。

code

//@Author: wxyww

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<ctime>

#include<cmath>

#include<map>

#include<string>

using namespace std;

typedef long long ll;

const int N = 5000010;

ll read() {

	ll x = 0,f = 1; char c = getchar();

	while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}

	while(c >= '0' && c <= '9') {x = x * 10 + c - '0',c = getchar();}

	return x * f;

}

ll dis[N];

int prmjs,vis[N];

ll n;

ll js,cnt[15];

void fj(ll x) {

	for(int i = 1;dis[i] * dis[i] <= x;++i) {

		if(x % dis[i] == 0) {

			cnt[++js] *= dis[i];

			x /= dis[i];

		}

		while(x % dis[i] == 0) x /= dis[i],cnt[js] *= dis[i];

	}

	if(x != 1) cnt[++js] = x;

}

ll ans;

ll exgcd(ll a,ll b,ll &x,ll &y) {

   if(b == 0) {

      x = 1,y = 0;return a;

  	}

   ll tmp = exgcd(b,a % b,x,y);

   ll t = x;

   x = y; y = t - a / b * y;

   return tmp;

}

int main() {

	int T = read();

	for(int i = 2;i <= 2000000;++i) {

		if(!vis[i]) dis[++prmjs] = i;

		for(int j = 1;j <= prmjs && 1ll * dis[j] * i <= 1000000;++j) {

			vis[dis[j] * i] = 1;

			if(i % dis[j] == 0) break;

		}

	}

	while(T--) {

		n = read() * 2;

		js = 0;

		for(int i = 1;i <= 14;++i) cnt[i] = 1;

		fj(n);

		ans = n * 2;

		ll m = 1 << js;

		for(int i = 0;i < m;++i) {

			ll now = 1;

			for(int j = 0;j < js;++j) if(i >> j & 1) now *= cnt[j + 1];

			ll x,y;

			exgcd(now,n / now,x,y);

			y = y % now;

			if(y >= 0) y -= now;

			ans = min(ans,n / now * -y);

		}

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

	}

	return 0;

}

巴特西

CometOJ10C 鱼跃龙门

problem

solution

code

最新文章

热门文章