RT，对了Sub 1246，错了七个点(8/整个Sub5/25/28/29)

思路是先处理每条边，求出其新的值(每个质因数次数膜k后的)和唯一一个与其相乘合法的值；然后拓扑一下，反着边判合法边DP，最后取最大值。

代码如下：

// Problem: P6381 『MdOI R2』Odyssey
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6381
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define M 200005//数据范围
#define O 10//质因数个数
// #define int long long //加这个会出奇怪的错
const int Li=350;//找质数时的限制,比sqrt(1e5)大
struct node//一条边的数据,包含边的基础信息,长度分解的质因数后的,以及思路里提到的两个值
{
	int s,t,L,W,ww,cnt,ct[O],num[O];
	//s=u,t=v,L=l,W和ww即思路里的那两个,前者是这条边的,后者是需要的
	//cnt是质因数个数,num[i]是质因数,ct[i]是每个num[i]次数,这些TopoDP的时候用不到了
}rd[M],fc;//最多有8个质因数,不慌
vector<int>road[M];//存路,链式前向行不回
queue<int>q;//拓扑用
map<int,int>f[M];//DP用,定义下面DP函数写了
int n,m,kp,P[Li],ans,Pcnt,vis[M],topo[M],out[M],in[M];//topo存顺序
//nmkp是nmk,P是质数,Pcnt先是质数个数后面用来拓扑,vis,out,in都如其名
bool CHPR(int x)//CHeck PRime
{
	for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
	return 1;
}
void YCLP() {for(int i=2;i<=Li;i++) if(CHPR(i)) P[++Pcnt]=i;}
//Yu Chu Li Prime
void Dod(int u,int v,int w,int l,int bh)//处理每条边
{
	ans=max(ans,l),rd[bh].s=u,rd[bh].W=rd[bh].ww=1,rd[bh].t=v,rd[bh].L=l,out[u]++,in[v]++,road[u].push_back(bh);int tsj,asd=w;
	//ans这里是因为"一条边也是完美路径"
	//W和ww是1,因为后面要乘其他的,tsj记录去0后多少质因数,asd调试的时候用的,可以删
	for(int i=1;P[i]*P[i]<=w;i++)
	{
		if(w%P[i]==0) rd[bh].num[++rd[bh].cnt]=P[i];//先存下这个数
		while(w%P[i]==0) rd[bh].ct[rd[bh].cnt]++,w/=P[i];//记录次数
		rd[bh].ct[rd[bh].cnt]%=kp;//取模
	}
	if(w!=1) rd[bh].ct[++rd[bh].cnt]=(1%kp),rd[bh].num[rd[bh].cnt]=w; tsj=rd[bh].cnt;
	for(int i=1;i<=rd[bh].cnt;i++) if(!rd[bh].ct[i]&&tsj--) for(int j=i+1;j<=rd[bh].cnt;j++) rd[bh].ct[j-1]=rd[bh].ct[j],rd[bh].num[j-1]=rd[bh].num[j]; rd[bh].cnt=tsj;//如果还剩一个质因数,因为我们处理质因数只处理到了sqrt(1e5)左右
	for(int i=1;i<=rd[bh].cnt;i++) 	rd[bh].W*=pow(rd[bh].num[i],rd[bh].ct[i]),rd[bh].ww*=pow(rd[bh].num[i],(kp-(rd[bh].ct[i])));//求两个值
	// cout<<endl<<rd[bh].W<<' '<<rd[bh].ww<<endl;
	// printf("第%d条边,数据:\n u=%d,v=%d,Len=%d,w=%d,质因数个数是%d,而质因数分别是:\n",bh,u,v,l,asd,rd[bh].cnt);
	// for(int i=1;i<=rd[bh].cnt;i++) printf("%d^%d  ",rd[bh].num[i],rd[bh].ct[i]); puts("");
	//以上调试用
}
void Topo()//正常的拓扑
{
	int up;//存队首
	for(int i=1;i<=n;i++) if(!in[i]) q.push(i),topo[++Pcnt]=i;//先把没有入边的怼进去
	while(!q.empty())
	{
		up=q.front(),q.pop();
		for(int i=0;i<road[up].size();i++)
		{
			fc=rd[road[up][i]];//为了方便
			in[fc.t]--;if(!in[fc.t]) q.push(fc.t),topo[++Pcnt]=fc.t;//如果删了这个点没有入边了就怼进去
		}
	}
}
void DP()//正常的DP
{
	//设f[i][j]表示若上一条边的w是j,走到的i开始的最长路,第二维用map
	reverse(topo+1,topo+1+n);//要反着枚举
	for(int cc=1,u=topo[cc],v;cc<=n;cc++,u=topo[cc])//u表示现在是哪个点
	{
		if(!out[u]) continue;//没有v就不用处理了,其实这条加不加区别不大
		for(int i=0;i<road[u].size();i++)
		{
			fc=rd[road[u][i]],v=fc.t;
			f[u][fc.ww]=max(f[u][fc.ww],fc.L+f[v][fc.W]);//因为是fc.W/ww,所以一定是合法的,换句话说如果v中间没有这个值的边那f[v][w]一定是0
			ans=max(ans,f[u][fc.ww]);//取最大值,每个点都可能是最长完美路径的开头
			// printf("f[%d][%d] now is %d\n",u,fc.ww,f[u][fc.ww]); //调试用
		}
	}
	cout<<ans<<endl;
}
signed main()
{
	cin>>n>>m>>kp,YCLP();//预处理
	for(int i=1,u,v,w,l;i<=m;i++) cin>>u>>v>>w>>l,Dod(u,v,w,l,i);//处理每条边
	Pcnt=0,Topo(),DP();//拓扑DP,输出在DP里
	return 0;
}