Znzryb's Blog
0%

Posted on Edited on

思路讲解

__int128大概可以表示1.7e38大小的数

image

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll A[MAXN];
__int128 N,M;

__int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

inline void solve(){
	N=read();M=read();
	print(N+M);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

给你一个正整数N。判断是否存在一对正整数(x,y)，使得x3−y3=N.如果存在这样的一对，请打印这样的一对(x,y)。给你一个正整数 N 。判断是否存在一对正整数 (x,y) ，使得 x^3 - y^3 = N .\\如果存在这样的一对，请打印这样的一对 (x,y) 。

这个形式还是很简单的，但是字少，可能还是比较难的。这其实也算是一个丢番图方程。

根据数理逻辑，非线形丢番图方程一般无法直接求解，所以基本靠枚举去解。

image

暴力枚举d即可，d的上界是N1/3N^{1/3}，1e6，是可以解决的。

然后这道题目上界比较大

AC代码

https://atcoder.jp/contests/abc397/submissions/64414819

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
// Problem: D - Cubes
// Contest: AtCoder - OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397)
// URL: https://atcoder.jp/contests/abc397/tasks/abc397_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
typedef __int128 i128;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

void print(i128 x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

inline void solve(){
	cin>>N;
	ll upD=ceil(pow((long double)N,(double)1/3));
// #ifdef LOCAL
    // cerr << upD << '\n';
// #endif
	// 枚举d
	for(__int128 d=1;d<=upD;++d){
		// 判断在这个d的条件下，y是不是合法的（是正整数吗？）
		__int128 delta=-3*d*d*d*d+12*d*N;
		if(delta<0) continue;
		i128 sqrtDel=sqrt(delta);
		if(sqrtDel*sqrtDel==delta){	// 验证delta为平方数
			i128 y=(-3*d*d+sqrtDel)/(6*d);
			if(y<=0) continue;
			if(y*6*d==(-3*d*d+sqrtDel)){	// 验证整除
				print(y+d);
				putchar(' ');
				print(y);
				return;
			}
		}
// #ifdef LOCAL
    // if(d==276544){
		// cerr<<"OK"<<"\n";
	// }
// #endif
		
	}
	cout<<-1<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc397/submissions/64414819
*/

心路历程（WA，TLE，MLE……）

1
ceil(pow((long double)N,(double)1/3));

小心C++隐式类型转换

Posted on Edited on

思路讲解

还是要再想一会，因为洛谷标签里只有树状数组。

说明理论上来说，你只要会求逆序对就会这题？但愿如此。

其实还是不难的，多写吧，写下来，你自然就懂了

注意，产生的逆序对是对于old序列，比他们小而且在他们后面的是对于new序列

现在的问题就在于怎么求这两个东西了。但其实很简单，因为他们在old里是0（最小的），在new里是m-1（最大的）

AC代码

https://atcoder.jp/contests/abc396/submissions/64400231

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// Problem: F - Rotated Inversions
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN],B[MAXN];
vector<ll> pos[MAXN];
ll tr[MAXN];
ll sumApos[MAXN];
ll rsumApos[MAXN];

inline ll lowbit(const ll &x){
	return (x&(-x));
}

inline void add(ll p,ll x){
	while(p<=M){
		tr[p]+=x;
		p+=lowbit(p);
	}
}

inline ll findBig(ll x,ll sum){
	ll res=0;
	while(x>0){	// 先找小于x，再用总数减掉找到的
		res+=tr[x];
		x-=lowbit(x);
	}
	res=sum-res;
	return res;
}

inline void solve(){
	cin>>N>>M;
	FOR(i,1,N){
		cin>>A[i];
		B[i]=(A[i]+M-1)%M;
		pos[A[i]].pb(i);
	}
	vector<ll> ans;
	// 先运用树状数组+频数数组得到初始B的逆序对数量
	ll lans=0;
	FOR(i,1,N){
		// 树状数组无法正确处理0，我们把映射整体提一个1
		lans+=findBig(B[i]+1,i-1);	// 前面一共i-1个数
		add(B[i]+1,1);
	}
// #ifdef LOCAL	// lans 正确运行
    // cerr << lans << '\n';
// #endif
	ans.pb(lans);
	FOR(i,0,M-1){
		ll cnt=0;
		for(int j=0;j<pos[i].size();++j){
			++cnt;
			sumApos[i]+=pos[i][j]-cnt;
		}
	}
	FOR(i,0,M-1){
		ll cnt=0;
		for(int j=0;j<pos[i].size();++j){
			rsumApos[i]+=N-pos[i][j]-cnt;
			++cnt;
		}
	}
// #ifdef LOCAL
   	// FOR(i,0,M-1){
   		// cerr<<sumApos[i]<<" ";
   	// }
   	// cerr<<"\n";
// #endif
	ll upAns=lans;
	ROF(i,M-1,1){
		ll ians=0;
		ll idx=M-(i);
		ians=upAns-sumApos[idx]+rsumApos[idx];
		ans.pb(ians);
		upAns=ians;
	}
	reverse(all(ans));
	for(int i=0;i<ans.size();++i){
		cout<<ans[i]<<"\n";
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc396/submissions/64400231
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

我们计算机嘛，这个推导对于我来说还是有点难了，不过结论很简单，就是b^(m-2)为其乘法逆元。

当然，你会说这个乘法逆元有什么用？ AcWing 886. 费马小定理， 快速幂， 求组合数 II  

这不求组合数就有用了吗！

参考以下题解

https://www.acwing.com/solution/content/16482/

image

AC代码

https://www.acwing.com/problem/content/submission/code_detail/40913617/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Problem: 快速幂求逆元
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/878/
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

ll binpow(ll a,ll k,const ll &p){
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

inline void solve(){
	ll a,p;
	cin>>a>>p;
	if(a%p==0) cout<<"impossible\n";
	else cout<<binpow(a,p-2,p)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.acwing.com/problem/content/submission/code_detail/40913617/
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

参考以下题解

https://www.acwing.com/solution/content/15293/

这里有一个非递归写法

https://www.acwing.com/solution/content/16482/

AC代码

https://www.acwing.com/problem/content/submission/code_detail/40911595/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Problem: 快速幂
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/877/
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;

ll binpow(ll a,ll k,const ll &p){
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

inline void solve(){
	ll a,k,p;
	cin>>a>>k>>p;
	cout<<binpow(a,k,p)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.acwing.com/problem/content/submission/code_detail/40911595/
*/

心路历程（WA，TLE，MLE……）