Protecting The Earth

（圆内取点） 

题目描述：

给定 K (地球上的人数)，你必须制作一个保护罩来保护他们。(地球上的人数），你必须制作一个保护罩来保护他们。

已知一个人只能站在整数的坐标上，并且两个人不能站在同一个地方，求以 (0,0) 坐标为圆心，能容纳 K 人的圆的最小个整数半径。

 输入样例：

3

2

6

13

输出样例： 

1

2

2 

AC代码 

# include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {int n;cin >> n;int l = 0, r = n;auto check = [&](int x)->bool{int cnt = 0;int my = x;for (int i = 1; i<=x; i++){while (i*i+my*my > x*x){my--;}cnt += my+1;}return 4*cnt+1 >= n;};while (l+1 < r){int mid = (l+r)/2;if (check(mid)) r = mid;else l = mid;}cout << r << endl;
}
signed main() {int t; cin >> t;while (t--) solve();return 0;
}

圆上的整点

（圆周取点） 

 求一个给定的圆，在圆周上有多少个点的坐标是整数。

输入格式 

输出格式

整点个数

 AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long int
#define eps 1e-9
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
LL n,ans = 0;
inline int gcd(int a,int b){return !b ? a : gcd(b,a % b);}
void check(LL d){LL R = 2 * n / d,E = (LL)sqrt(R),v;for (int i = 1; i < E; i++){v = (LL)sqrt(R - i * i);if (gcd(i,v) == 1 && i <= v &&i * i + v * v == R) ans++;}
}
int main()
{cin >> n;LL E = (LL)sqrt(2.0 * n);for (int i = 1; i <= E; i++){if (2 * n % i) continue;if (i * i == 2 * n) check(i);else check(i),check(2 * n / i);}cout<<4 * ans + 4<<endl;return 0;
}