hyfb

5693

hyfb
4个月前
#include <cstdio>
#include <queue>
#include <iostream>

using namespace std;

int main(){
int T;
scanf("%d",&T);
while(T --){
int n,m;
scanf("%d%d",&m,&n);
printf("%d %d\n",m,(n + 1) / 2);

priority_queue<int> down;
priority_queue<int, vector<int>,greater<int> > up;

int cnt = 0;
for(int i = 1; i <= n; i ++){
int x;
scanf("%d",&x);
if(down.empty() || x <= down.top())down.push(x);
else up.push(x);

if(down.size() > up.size() + 1) up.push(down.top()),down.pop();
if(up.size() > down.size()) down.push(up.top()),up.pop();

if(i % 2){
printf("%d ",down.top());
if(++ cnt % 10 == 0)puts("");
}

}
if(cnt % 10)puts("");
}
return 0;
}


hyfb
5个月前
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int N = 2e5+7,M = 18;
int f[N][M],w[N],n,m;
void init(){
for(int j = 0; j <= M; j ++){
for(int i = 1; i + (1 << j) - 1 <= n; i ++){
if(!j)f[i][j] = w[i];
else f[i][j] = max(f[i][j - 1],f[i + (1 << j - 1)][j - 1]);
}
}
}

int query(int l,int r){
int len = r - l + 1;
int k = log(len) / log(2);
return max(f[l][k],f[r - (1 << k) + 1][k]);
}

int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i ++)scanf("%d",&w[i]);
init();
scanf("%d",&m);
for(int i = 1; i <= m; i ++){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}

}


hyfb
5个月前
#include <iostream>
using namespace std;

#define LL long long

int gcd(int a,int b){
return b ? gcd(b, a % b) : a;
}
LL qmi(LL a,LL b,LL p){
int t = b - 2;
LL res = 1;
while(t){
if(t & 1)res = res * a % p;
a = a * a % p;
t >>= 1;
}
return res;
}
int main(){
int n;
cin >> n;
while(n --){
int ai,pi;
cin >> ai >> pi;
if(ai % pi)cout << qmi(ai,pi,pi) << endl;
else cout << "impossible" << endl;
}
return 0;
}


hyfb
5个月前
#include <iostream>
using namespace std;
typedef long long LL;

int gcd(int a,int b){
return b ? gcd(b, a % b) : a;
}

LL C(int n)//c(3,n)
{
return (LL)n * (n - 1) * (n - 2) / 6;
}

int main(){
int n,m;
cin >> n >> m;
n ++,m ++;
LL res = C(n * m) - (LL)n * C(m) - (LL)m * C(n);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++){
res -= 2ll * (gcd(i,j) - 1) * (n - i) * (m - j);
}
cout << res << endl;
}


hyfb
5个月前
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 150;//150位

int k,x;
int f[1000][100][N];

int qmi(int a,int b,int p){
int res = 1 % p;
while(b){
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

for(int i = 0,t = 0; i < N; i ++){
t += a[i] + b[i];
c[i] = t % 10;
t /= 10;
}
}
int main(){
cin >> k >> x;
int n = qmi(x % 1000,x,1000);

for(int i = 0; i < n; i ++)
for(int j = 0; j <= i && j < k; j ++)
if(!j)f[i][j][0] = 1;
else add(f[i][j],f[i - 1][j - 1] , f[i - 1][j]);

int *g = f[n - 1][k - 1];
int i = N - 1;
while(!g[i]) i --;
while(i >= 0)cout << g[i--];
}



hyfb
5个月前

# include [HTML_REMOVED]

using namespace std;

const int N = 1e5 + 7,mod = 5000011;
int n,k;
int f[N],s[N];

int main()
{
cin >> n >> k;

f[0] = s[0] = 1;
for(int i = 1; i <= n; i ++){
f[i] = s[max(i - k - 1,0)];
s[i] = (s[i - 1] + f[i]) % mod;
}
cout << s[n] << endl;
return 0;


}

hyfb
5个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 10;

int n;
int A[N], B[N];

void exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b) x = 1, y = 0;
else
{
exgcd(b, a % b, y, x);
y -= a / b * x;
}
}

int main()
{
scanf("%d", &n);

LL M = 1;
for (int i = 0; i < n; i ++ )
{
scanf("%d%d", &A[i], &B[i]);
M *= A[i];
}

LL res = 0;
for (int i = 0; i < n; i ++ )
{
LL Mi = M / A[i];
LL ti, x;
exgcd(Mi, A[i], ti, x);
res += B[i] * Mi * ti;
}

cout << (res % M + M) % M << endl;

return 0;
}



hyfb
5个月前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long LL;

LL qmul(LL a,LL k,LL b){
LL res = 0;
while(k){
if(k & 1) res = (res + a) % b;
a = (a + a) % b;
k >>= 1;
}
return res;
}

LL qmi(LL a,LL k,LL b){
LL res = 1 % b;
while(k){
if(k & 1) res = qmul(res,a,b);
a = qmul(a,a,b);
k >>= 1;
}
return res;
}
LL get_euler(LL C){
LL res =  C;
for(LL i = 2; i <= C / i; i ++){
if(C % i == 0){
while(C % i == 0) C /= i;
res = res / i * (i - 1) ;//防止溢出先除后乘
}
}
if(C > 1) res = res / C * (C - 1);
return res;
}
int main(){
int T = 1;
LL L;
while(cin >> L,L){
int d = 1;
while(L % (d * 2) == 0 && d * 2 <= 8)d *= 2;
LL C = 9 * L / d;
LL phi = get_euler(C);

LL res =  1e18;
if(C % 2 == 0 || C % 5 == 0)res = 0;

for(LL d = 1; d * d <= phi; d ++)
if(phi % d == 0)
{
if(qmi(10,d,C) == 1)res = min(res,d);
if(qmi(10,phi / d,C) == 1)res = min(res,phi / d);
}

printf("Case %d: %lld\n",T ++,res);
}
return 0;
}


hyfb
5个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int exgcd(LL a,LL b,LL &x,LL &y){
if(!b){
x = 1, y = 0;
return a;
}

LL d = exgcd(b,a % b,y,x);
y -= a / b * x;
return d;
}
int main(){
LL a,b,m,n,L;
cin >> a >> b >> m >> n >> L;

LL x,y;
LL d = exgcd(m - n, L ,x,y);

if((b - a) % d)puts("Impossible");
else{
x *= (b - a) / d;
LL t = abs(L / d);
cout << (x % t + t) % t << endl;
}

return 0;
}


hyfb
5个月前
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int exgcd(int a,int b,int &x,int &y){
if(!b){
x = 1, y = 0;
return a;
}
int d = exgcd(b,a % b, y, x);
y -= a / b * x;

return d;
}
int main(){
int a,b,x,y;
cin >> a >> b;
exgcd(a,b,x,y);
cout << (x % b + b) % b << endl;
return 0;
}