首页 > 其他分享 >[ARC144E]GCD of Path Weights

[ARC144E]GCD of Path Weights

时间:2023-01-23 11:11:06浏览次数:60  
标签:10 GCD leq beautifulness Vertex maximum Sample ARC144E Weights

Problem Statement

You are given a directed graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1, 2, \ldots, N$. The $i$-th edge is directed from Vertex $a_i$ to Vertex $b_i$, where $a_i < b_i$.

The beautifulness of a sequence of positive integers $W = (W_1, W_2, \ldots, W_N)$ is defined as the maximum positive integer $x$ that satisfies the following:

  • For every path $(v_1, \ldots, v_k)$ ($v_1 = 1, v_k = N$) from Vertex $1$ to Vertex $N$ in $G$, $\sum_{i=1}^k W_{v_i}$ is a multiple of $x$.

You are given an integer sequence $A = (A_1, A_2, \ldots, A_N)$. Find the maximum beautifulness of a sequence of positive integers $W = (W_1, \ldots, W_N)$ such that $A_i \neq -1 \implies W_i = A_i$. If the maximum beautifulness does not exist, print -1.

Constraints

  • $2\leq N\leq 3\times 10^5$
  • $1\leq M\leq 3\times 10^5$
  • $1\leq a_i < b_i \leq N$
  • $(a_i,b_i)\neq (a_j,b_j)$ if $i\neq j$
  • In the given graph $G$, there is a path from Vertex $1$ to Vertex $N$.
  • $A_i = -1$ or $1\leq A_i\leq 10^{12}$

Input

Input is given from Standard Input in the following format:

$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the maximum beautifulness of a sequence of positive integers $W$. If the maximum beautifulness does not exist, print -1.


Sample Input 1

4 4
1 2
1 3
2 4
3 4
-1 3 7 -1

Sample Output 1

4

There are two paths from Vertex $1$ to Vertex $N$: $(1,2,4)$ and $(1,3,4)$. For instance, $W = (5, 3, 7, 8)$ has a beautifulness of $4$. Indeed, both $W_1 + W_2 + W_4 = 16$ and $W_1 + W_3 + W_4 = 20$ are multiples of $4$.


Sample Input 2

4 5
1 2
1 3
2 4
3 4
1 4
-1 3 7 -1

Sample Output 2

1

There are three paths from Vertex $1$ to Vertex $N$: $(1,2,4)$, $(1,3,4)$, and $(1,4)$. For instance, $W = (5, 3, 7, 8)$ has a beautifulness of $1$.


Sample Input 3

4 4
1 2
1 3
2 4
3 4
3 -1 -1 7

Sample Output 3

-1

For instance, $W = (3, 10^{100}, 10^{100}, 7)$ has a beautifulness of $10^{100}+10$. Since you can increase the beautifulness of $W$ as much as you want, there is no maximum beautifulness.


Sample Input 4

5 5
1 3
3 5
2 3
3 4
1 4
2 -1 3 -1 4

任意一条从 1 到 \(n\) 的路径都是 \(x\) 的倍数,这是一个很固定的要求。比如现在有这样的两条路径:
image
那么 \(w_2+w_3+w_n=w_2+w_4+w_n(\bmod x)\)
\(w_2+w_3+w_n-w_2-w_4-w_n=0(\bmod x)\)

这启发我们建一条反边,权值取反。

但权值在点上啊

拆点,把一个点拆成两个,中间的边的正的方向边权是点的权值,反的方向是点的权值取负。原来的单向边改为双向边,权值为0。此时我们想要让图只有 0 环。

只有0环的图有什么特点?从任意一个点出发,到某一个点的任意路径长度相等(又绕回了开头)。

那么如果此时从 \(1\) 开始搜索,到达某一个点有一条路径距离 \(d\),另一条是 \(w\),那么 \(x\) 整除 \(|d-w|\)

这样子不断求gcd,可以得到 \(x\) 的限制。

但是如果点权为 \(-1\)?拆出来的两个点不连边。因为中间这条边可以随意决定。

注意要特判如果 \(1\) 到 \(n\) 是一个连通块,那么 \(x\) 要和 \(d_n\) 求一个 gcd.

小细节:所有 1 到不了的点和到不了 \(n\) 的点都是不影响 \(x\) 的,要去掉。

真的算一个神题了,知识点最难的也就dfs,但 rated 直飙 3280

标签:10,GCD,leq,beautifulness,Vertex,maximum,Sample,ARC144E,Weights
From: https://www.cnblogs.com/mekoszc/p/17065049.html

相关文章

  • GCD辗转相除的经典套路
      2543.判断一个点是否可以到达-力扣(Leetcode)前两个移动很像辗转相除法(这个套路在Codeforces上已经出烂了)<br>后两个移动可以让 g 乘上$2^k$classS......
  • exgcd & 线性同余方程
    前置芝士裴蜀定理exgcdexgcd即扩展欧几里得定理,常用来求解\(ax+by=gcd(a,b)\)的可行解问题推导过程:考虑我们有:​ \(ax+by=gcd(a,b)\)——裴蜀定理​ \(a_......
  • leetcode 每日一题 gcd+枚举
    1819.序列中不同最大公约数的数目给你一个由正整数组成的数组nums。数字序列的最大公约数定义为序列中所有整数的共有约数中的最大整数。  例如,序列[4,6,16]......
  • abc254 F - Rectangle GCD
    题意:给定等长的正整数组\(a[],b[]\),它们确定了一个矩阵\(A_{i,j}=a_i+b_j\)。\(q\)次询问,回答矩阵中一个矩形区域内所有数的\(\gcd\)\(n,q\le2e5\)思路:差分,绝对......
  • Apple开发_使用 GCDAsyncUdpSocket 发送组播消息报错"No route to host"的解决
    1、问题描述苹果手机升级到ios14.5系统后,使用GCDAsyncUdpSocke发送组播消息的时候,发现报错了,ErrorDomain=NSPOSIXErrorDomainCode=65"Noroutetohost"UserInfo=......
  • 扩展欧几里得(exgcd(a,b))
    回顾       由贝祖定理可知:ax+by=gcd(a,b)       (a,y)为一组解      (x+kb,y-ka)也为解       所以有无数组解一、扩展欧几里得算法......
  • gcd(a, b, c) = gcd(gcd(a, b), c)
    某一天,我正苦逼的刷题看题解,看到下面的代码inttmp=0; for(inti=1;i<=n;++i){ scanf("%d",&a[i]); tmp=gcd(tmp,a[i]); }​ 我心中一惊:wc,这就能求gcd(a1,a2......
  • P2398 GCD SUM——欧拉函数
    此题可以拓展为\(\sum\limits^n_{i=1}\sum\limits^m_{j=1}\gcd(i,j)\)结论是\(\sum\limits^{\min(n,m)}_{d=1}\varphi(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{......
  • Trick 5: 关于 GCD 的一些处理方法和性质
    经典的mobius:\(\varepsilon(x)=\sum\limits_{d|x}\mu(d)\)经典的euler:\(x=\sum\limits_{d|x}\varphi(d)\)处理区间问题。如果考虑一段区间的\(\gcd\),那......
  • 容斥原理与gcd的问题
    gcd个数的处理(i,j无限制)P2398GCDSUMi为1-n,j为1-m,求gcd为k的个数代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintM=1e5+5;......