#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll MAXN = 100005;
struct Node {
ll l, r;//l和r表示这一段的起点和终点
mutable ll v;//v表示这一段上所有元素相同的值是多少
Node(ll l, ll r = 0, ll v = 0) : l(l), r(r), v(v) {}
bool operator<(const Node &a) const {
return l < a.l;//规定按照每段的左端点排序
}
};
ll n, m, seed, vmax, a[MAXN];
set<Node> s;
//以pos去做切割,找到一个包含pos的区间,把它分成[l,pos-1],[pos,r]两半
set<Node>::iterator split(int pos) {
set<Node>::iterator it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos) {
return it;
}
it--;
if (it->r < pos) return s.end();
ll l = it->l;
ll r = it->r;
ll v = it->v;
s.erase(it);
s.insert(Node(l, pos - 1, v));
//insert函数返回pair,其中的first是新插入结点的迭代器
return s.insert(Node(pos, r, v)).first;
}
/*
* 这里注意必须先计算itr。
* 比如现在区间是[1,4],如果要add的是[1,2],如果先split(1)
* 那么返回的itl是[1,4],但是下一步计算itr的时候会把这个区间删掉拆成[1,2]和[3,4]
* 那么itl这个指针就被释放了
* */
void add(ll l, ll r, ll x) {
set<Node>::iterator itr = split(r + 1), itl = split(l);
for (set<Node>::iterator it = itl; it != itr; ++it) {
it->v += x;
}
}
void assign(ll l, ll r, ll x) {
set<Node>::iterator itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(Node(l, r, x));
}
struct Rank {
ll num, cnt;
bool operator<(const Rank &a) const {
return num < a.num;
}
Rank(ll num, ll cnt) : num(num), cnt(cnt) {}
};
ll rnk(ll l, ll r, ll x) {
set<Node>::iterator itr = split(r + 1), itl = split(l);
vector<Rank> v;
for (set<Node>::iterator i = itl; i != itr; ++i) {
v.push_back(Rank(i->v, i->r - i->l + 1));
}
sort(v.begin(), v.end());
int i;
for (i = 0; i < v.size(); ++i) {
if (v[i].cnt < x) {
x -= v[i].cnt;
} else {
break;
}
}
return v[i].num;
}
ll ksm(ll x, ll y, ll p) {
ll r = 1;
ll base = x % p;
while (y) {
if (y & 1) {
r = r * base % p;
}
base = base * base % p;
y >>= 1;
}
return r;
}
ll calP(ll l, ll r, ll x, ll y) {
set<Node>::iterator itr = split(r + 1), itl = split(l);
ll ans = 0;
for (set<Node>::iterator i = itl; i != itr; ++i) {
ans = (ans + ksm(i->v, x, y) * (i->r - i->l + 1) % y) % y;
}
return ans;
}
ll rnd() {
ll ret = seed;
seed = (seed * 7 + 13) % MOD;
return ret;
}
int main() {
cin >> n >> m >> seed >> vmax;
for (int i = 1; i <= n; ++i) {
a[i] = (rnd() % vmax) + 1;
s.insert(Node(i, i, a[i]));
}
for (int i = 1; i <= m; ++i) {
ll op, l, r, x, y;
op = (rnd() % 4) + 1;
l = (rnd() % n) + 1;
r = (rnd() % n) + 1;
if (l > r) swap(l, r);
if (op == 3) {
x = (rnd() % (r - l + 1)) + 1;
} else {
x = (rnd() % vmax) + 1;
}
if (op == 4) {
y = (rnd() % vmax) + 1;
}
if (op == 1) {
add(l, r, x);
} else if (op == 2) {
assign(l, r, x);
} else if (op == 3) {
cout << rnk(l, r, x) << endl;
} else {
cout << calP(l, r, x, y) << endl;
}
}
return 0;
}
int n, m;
int k, T, S, D;
struct edge{
int a, b, w;
bool operator <(const edge& ee)const { return w < ee.w; }
}ed[M];
vector<int> e[N]; //即为重构树
int d[N];
int p[N];
int find(int x) {
return p[x] == x ? p[x] : p[x] = find(p[x]);
}
int kruskal() {
sort(ed + 1, ed + 1 + m);
fer(i, 1, 2*n) p[i] = i;
int cnt = n; //虚点的节点编号
fer(i, 1, m) {
int a = find(ed[i].a), b = find(ed[i].b);
if (a^b){ //不在同一个连通块中,需要合并
d[++cnt] = ed[i].w; //建立虚点
p[a] = p[b] = cnt;
e[cnt].push_back(a);
e[cnt].push_back(b);
}
}
return cnt;
}
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include <unordered_map>
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second
#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
//#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
const int maxn = 1e6 + 7;
const int N = 1e6 + 7;
const int M = 5e6 + 7;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}
/*
真的难...
首先,搞清楚题意!!!
题目问的是删除的边的权值和最少是多少能够使得这个图的MST是唯一的;
(意思是删完之后还是个图,不是说删完就是一棵树了...)
题解参考这里:
https://blog.csdn.net/Mr_dimple/article/details/123999834?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E5%94%AF%E4%B8%80%E6%80%A7&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-123999834.142^v30^pc_rank_34,185^v2^control&spm=1018.2226.3001.4449
这个题解太神了,甚至不用去求次小生成树!!!
(细品题解!!!)
*/
int n,m;
struct node
{
int a,b,c;
}no[maxn];
int f[maxn];
int find(int x)
{
return f[x]==x ? x : f[x]=find(f[x]);
}
bool cmp(node no1,node no2)
{
return no1.c < no2.c;
}
int ans; //总共删除的边
int sum; //最小生成树的权值
void kruskal()
{
sort(no+1,no+1+m,cmp);
for(int i=1;i<=n;i++) f[i] = i;
for(int i=1;i<=m;i++)
{
int r = i; //双指针找出相同权值的边
while(r <= m && no[r].c == no[i].c) r++;
r--;
for(int j=i;j<=r;j++)
{
int a = no[j].a;
int b = no[j].b;
int c = no[j].c;
//边权相同且能连通不同连通块的,先全都删除
if(find(a) != find(b)) ans += c;
}
for(int j=i;j<=r;j++) //求最小生成树
{
int a = no[j].a;
int b = no[j].b;
int c = no[j].c;
if(find(a) != find(b))
{
sum += c;
f[find(a)] = find(b);
}
}
i = r;
}
ans -= sum; //剩下的就是要删除的边的权值和
}
int main()
{
iire(n,m);
for(int i=1;i<=m;i++)
{
int a,b,c;
iire(a,b);
ire(c);
no[i] = {a,b,c};
}
kruskal();
//这里如果ans=0,则说明此时最小生成树是唯一的
cout<<ans<<endl;
return 0;
}
void dfs(int u,int fa)
{
// for(int i=0;i<v[u].size();i++) //遍历与这个点相连的点
// {
// int zi = v[u][i]; //注意这里子节点是v[u][i]而不是i
//
// if(zi == fa) continue; //防止往回走
//
// dfs(zi,u); //一直dfs
//
// //回溯时向上更新(dp过程)...
// }
for(int i=h[u];i!=-1;i=ne[i])
{
int j = e[i];
if(j==fa) continue;
dfs(j,u);
//回溯时向上更新(dp过程)...
}
}
欧拉降幂:解决a^b % c (其中b是大数)
a^b % c = a^(b % f(c) + f(c)) % c
其中f(c)是c的欧拉函数
注意:
1. 多%两下,没问题的
2. 全部写成long long
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1000010;
ll qmi(ll a,ll b,ll p)
{
ll ans = 1;
while(b)
{
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans % p;
}
ll euler(ll x) //求欧拉函数
{
ll ans = x;
for(ll i=2; i<=x/i; i++)
{
if(x % i == 0)
{
ans = ans / i * (i-1);
while(x % i == 0) x /= i;
}
}
if(x > 1) ans = ans / x * (x-1);
return ans;
}
ll oulami(ll a,string b,ll c) //欧拉降幂
{
ll num = euler(c); //求c的欧拉函数
ll mi = 0;
//用取余的性质算就行
for(int i=0; i<b.length(); i++) mi = (mi * 10 + b[i] - '0') % num;
mi += num;
return qmi(a,mi,c); //快速幂
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll a,c;
string b;
cin>>a>>b>>c;
if(b[0] == '0') puts("1"); //这里注意特判,不然 0^0 会错
else cout<<(ll)oulami(a,b,c) % c<<endl;
}
return 0;
}