【AtCoder】Tenka1 Programmer Contest
2024-08-24 15:32:28
C - 4/N
列出个方程枚举解一下
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 4005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int64 N;
void Solve() {
read(N);
for(int64 i = 1 ; i <= 3500 ; ++i) {
for(int64 j = 1 ; j <= 3500 ; ++j) {
int64 t = 4 * i * j - N * j - N * i;
if(t <= 0) {continue;}
int64 s = N * i * j;
if(s % t == 0) {
out(s / t);space;out(i);space;out(j);enter;
return ;
}
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
D - IntegerotS
每次删掉一个lowbit，然后加上这个lowbit - 1
这样的话我们每次求一遍满足是这个数子集的数的和就行了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 100005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,K;
int A[MAXN],B[MAXN];
int64 ans;
int lowbit(int x) {
return x & (-x);
}
void Calc(int v) {
int64 res = 0;
for(int i = 1 ; i <= N ; ++i) {
if((v & A[i]) == A[i]) res += B[i];
}
ans = max(ans,res);
}
void Solve() {
read(N);read(K);
for(int i = 1 ; i <= N ; ++i) {
read(A[i]);read(B[i]);
}
Calc(K);
while(K) {
int t = lowbit(K);
int h = K - 1;
K -= t;
Calc(h);
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
E - CARtesian Coodinate
又是几何题。。。
二分次数150WA了改成200过了orz
肯定是这些点的横坐标的中位数和纵坐标的中位数
然后我们用纵坐标距离，二分一个数，画一条平行于x轴的线
然后求出交点，把每条线的交点从小到大排序，每条线能相交且在这个纵坐标值以下的线就是交点横坐标比它小且幅角比它大
树状数组维护一下就行了
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 40005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const db PI = acos(-1.0);
int N,id[MAXN],tr[MAXN];
int64 ALL;
db A[MAXN],B[MAXN],C[MAXN];
pair<db,int> t[MAXN];
int lowbit(int x) {
return x & (-x);
}
void Insert(int x) {
while(x <= N) {
tr[x]++;
x += lowbit(x);
}
}
int Query(int x) {
int res = 0;
while(x > 0) {
res += tr[x];
x -= lowbit(x);
}
return res;
}
bool dcmp(db a,db b) {
return fabs(a - b) < eps;
}
void Calc_y() {
for(int i = 1 ; i <= N ; ++i) {
t[i] = mp(atan2(-A[i],B[i]),i);
if(t[i].fi < 0) t[i].fi += PI;
}
sort(t + 1,t + N + 1);
for(int i = 1 ; i <= N ; ++i) id[t[i].se] = i;
db L = -1e9,R = 1e9;
int cnt = 200;
while(cnt--) {
db mid = (L + R) * 0.5;
int64 res = 0;
for(int i = 1 ; i <= N ; ++i) {
t[i] = mp((C[i] - B[i] * mid) / A[i],id[i]);
}
sort(t + 1,t + N + 1);
int p = N + 1;
memset(tr,0,sizeof(tr));
for(int i = N ; i >= 1 ; --i) {
if(i != N && !dcmp(t[i + 1].fi,t[i].fi)) {
res += 1LL * (p - i - 1) * (p - i - 2) / 2;
for(int j = p - 1 ; j >= i + 1; --j) {
Insert(t[j].se);
}
p = i + 1;
}
res += Query(t[i].se - 1);
}
res += 1LL * (p - 1) * (p - 2) / 2;
if(res >= (ALL + 1) / 2) R = mid;
else L = mid;
}
printf("%.10lf",R);
}
void Calc_x() {
for(int i = 1 ; i <= N ; ++i) {
t[i] = mp(atan2(-A[i],B[i]),i);
if(t[i].fi < 0) t[i].fi += PI;
if(t[i].fi * 2 > PI) t[i].fi -= PI;
}
sort(t + 1,t + N + 1);
for(int i = 1 ; i <= N ; ++i) id[t[i].se] = i;
db L = -1e9,R = 1e9;
int cnt = 200;
while(cnt--) {
db mid = (L + R) * 0.5;
int64 res = 0;
for(int i = 1 ; i <= N ; ++i) {
t[i] = mp((C[i] - A[i] * mid) / B[i],id[i]);
}
sort(t + 1,t + N + 1);
int p = 0;
memset(tr,0,sizeof(tr));
for(int i = 1 ; i <= N ; ++i) {
if(i != 1 && !dcmp(t[i - 1].fi,t[i].fi)) {
res += 1LL * (i - 1 - p) * (i - 1 - p - 1) / 2;
for(int j = p + 1 ; j <= i - 1 ; ++j) {
Insert(t[j].se);
}
p = i - 1;
}
res += Query(t[i].se - 1);
}
res += 1LL * (N - p) * (N - p - 1) / 2;
if(res >= (ALL + 1) / 2) R = mid;
else L = mid;
}
printf("%.10lf",R);
}
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) {
scanf("%lf%lf%lf",&A[i],&B[i],&C[i]);
}
ALL = 1LL * N * (N - 1) / 2;
Calc_x();space;Calc_y();enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}
F - ModularPowerEquation!!
有点神奇
我们根据欧拉定理，可以有
\(a^k \equiv a^{\varphi(m) + k % \varphi(m)} \pmod m\)
然后k如果大到一定程度，两个数\(a^{x}\)和\(a^{y}\)相同就是\(x\)和\(y\)在取模\(\varphi(m)\)意义下相同
设置他们都大于100
然后需要满足
\(x \equiv A^{y} \pmod M\)
\(x \equiv y \pmod {\varphi(m)}\)
根据扩欧，我们需要有
\(A^y \equiv y \pmod {gcd(M,\varphi(m))}\)
这个可以递归下去
然后假如我们求出了这个y
我们就可以代入原来的式子，解出一个x
如果x不够大，我们可以加上我们取模的数字，直到x大于100
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 40005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int64 A,M;
int64 phi(int64 x) {
int64 t = x;
for(int i = 2 ; i <= x / i ; ++i) {
if(x % i == 0) {
t = t / i * (i - 1);
while(x % i == 0) x /= i;
}
}
if(x > 1) t = t / x * (x - 1);
return t;
}
int64 gcd(int64 a,int64 b) {
return b == 0 ? a : gcd(b,a % b);
}
int64 fpow(int64 x,int64 c,int64 M) {
int64 res = 1,t = x;
while(c) {
if(c & 1) res = res * t % M;
t = t * t % M;
c >>= 1;
}
return res;
}
void exgcd(int64 a,int64 b,int64 &x,int64 &y) {
if(b == 0) {x = 1;y = 0;}
else {
exgcd(b,a % b,y,x);
y -= a / b * x;
}
}
int64 mul(int64 a,int64 b,int64 M) {
int64 res = 0,t = a;
while(b) {
if(b & 1) res = (res + t) % M;
t = (t + t) % M;
b >>= 1;
}
return res;
}
int64 Calc(int64 a,int64 m) {
if(m == 1) return 100;
int64 eu = phi(m),g = gcd(eu,m);
int64 y = Calc(a,g);
int64 a1 = fpow(a,y,m),a2 = y % eu;
int64 x,t;
exgcd(m,eu,x,t);
int64 mod = m * eu / g;
x = (x % (eu / g) + eu / g) % (eu / g);
x = x * (a2 - a1) / g;
x = (x % mod + mod) % mod;
x = (mul(x,m,mod) + a1) % mod;
while(x < 100) x += mod;
return x;
}
void Solve() {
read(A);read(M);
int64 x = Calc(A,M);
out(x);enter;
//if(fpow(A,x,M) == x % M) {puts("YES");}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
int Q;
read(Q);
while(Q--) Solve();
}
最新文章
- Android动画：模拟开关按钮点击打开动画（属性动画之平移动画）
- oracle数据库的安装、配置与无残留卸载
- Redmine性能测试
- 【转载】Java中的回车换行符/n /r /t
- Git.Framework 框架随手记--准备工作
- Java Serializable（序列化）
- IBatis.Net 表连接查询(五)
- Drainage Ditches(Dinic最大流)
- 理解 Linux 网络栈（1）：Linux 网络协议栈简单总结 图
- Geodatabase - 删除要素
- JavaScript学习之获取URL参数
- UVALive 7070 The E-pang Palace（暴力）
- 4.0、Android Studio配置你的构建
- cmd 【已解决】windows连接手机，运行adb devices提示“unauthorized”
- 开源jar包bug导致的CPU消耗200%问题分析案例
- seelog 文件输出格式
- MD5 哈希等各种加密方式 都是对这个对象进行各种运算， 然后得出1个字符串
- 并发集合 System.Collections.Concurrent 命名空间
- Hdu5181 numbers
- Linux 删除文件后空间不释放【原创】