AtCoder Beginner Contest 166

AtCoder Beginner Contest 166

D - I hate Factorization

Question

求任意一组满足 $A^5-B^5=X$A5−B5=X的 $A$A 和 $B$B。
保证必有解。 $1\le X\le 10^9$1≤X≤109

Solution

暴力出奇迹，由于 $100^5>10^9$1005>109，所以找一个范围直接暴力求即可。
$O\left(n^2\right)$O(n2) $n=200$  n=200
第一发交了一发n为100的，没覆盖全，然后想会不会漏掉了，然而其实就是数据范围开太小了，开个200就过了。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll x;cin>>x;
	for(ll i=0;i<=200;i++){
		for(ll j=-i;j<=i;j++){
			if(i*i*i*i*i-j*j*j*j*j==x){cout<<i<<" "<<j<<'\n';return 0;}
		}
	}
	return 0;
}

E - This Message Will Self-Destruct in 5s

Question

求满足 a[i]+a[j]=j−i  (i<j)的组数。

Solution

移项 a[i]+i=−a[j]+j  (i<j)
开个map记录所有的 $a\left[i\right]+i$a[i]+i，每次检查是否存在 $-a\left[j\right]+j$−a[j]+j，若加上对应的贡献。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	unordered_map<int,int>M;
	ll ans=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		M[-x-i]++;
		if(M.count(x-i)) ans+=M[x-i];
	}
	cout<<ans<<'\n';
	return 0;
}