怎么搭建php网站,站长素材音效,会计培训班推荐,企业手机端网站设计模板problem
luogu-P2065
solution
这个拿走一组共两张卡片的操作其实就是一个匹配。
直接两个数的最大公约数大于 111 就建一条边#xff0c;跑二分图匹配最大流即可。
然而如果直接枚举两个数然后算他们的 gcd\text{gcd}gcd #xff0c;时间复杂度 O(Tn2logV)O(Tn^2\log…problem
luogu-P2065
solution
这个拿走一组共两张卡片的操作其实就是一个匹配。
直接两个数的最大公约数大于 111 就建一条边跑二分图匹配最大流即可。
然而如果直接枚举两个数然后算他们的 gcd\text{gcd}gcd 时间复杂度 O(Tn2logV)O(Tn^2\log V)O(Tn2logV) 会 TLE\text{TLE}TLE。
又不能预处理任意两个数的 gcd\text{gcd}gcd这个数字 ∈(1,1e7)\in(1,1e7)∈(1,1e7) 实在是太大了。
这里很巧妙任何数都可以拆成若干个质数的幂两个数的 gcd1\text{gcd}1gcd1 无非就是两个数有相同的某些个质因子。
所以我们可以预处理出 1e71e71e7 以内的所有质数这并不多然后将一个数和其质因子连边。
只显然每张卡片只能拿走一次流量与源汇点之间为 111 即可。
这样时间复杂度就是 O(Tnn)O(Tn\sqrt{n})O(Tnn) 网络流就没考虑反正是 O(O(O( 能过 )))。
code
#include bits/stdc.h
using namespace std;
#define maxn 100005
#define maxm 800005
int T, m, n, s, t, cnt -1, tot;
struct node { int to, nxt, flow; }E[maxm];
int b[maxn], r[maxn], head[maxn], cur[maxn], dep[maxn];
queue int q;int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y );
}void addedge( int u, int v, int w ) {E[ cnt] { v, head[u], w }, head[u] cnt;E[ cnt] { u, head[v], 0 }, head[v] cnt;
}bool bfs() {memset( dep, 0, sizeof( dep ) );memcpy( cur, head, sizeof( head ) );dep[s] 1; q.push( s );while( ! q.empty() ) {int u q.front(); q.pop();for( int i head[u];~ i;i E[i].nxt ) {int v E[i].to;if( ! dep[v] and E[i].flow ) {dep[v] dep[u] 1;q.push( v );}}}return dep[t];
}int dfs( int u, int cap ) {if( u t or ! cap ) return cap;int flow 0;for( int i cur[u];~ i;i E[i].nxt ) {cur[u] i; int v E[i].to;if( dep[v] dep[u] 1 ) {int w dfs( v, min( cap, E[i].flow ) );if( ! w ) continue;E[i ^ 1].flow w;E[i].flow - w;flow w;cap - w;if( ! cap ) break;}}return flow;
}int dinic() {int ans 0;while( bfs() ) ans dfs( s, 1e9 );return ans;
}#define maxp 10000005
int prime[maxp], vis[maxp], num[maxp];
int cntp;
void sieve() {for( int i 2;i 1e7;i ) {if( ! vis[i] ) prime[ cntp] i;for( int j 1;j cntp and i * prime[j] 1e7;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) break;}}
}
void divide( int id, int val ) {for( int i 1;i cntp and prime[i] val;i ) if( val % prime[i] 0 ) {if( ! num[prime[i]] ) num[prime[i]] tot;if( id m ) addedge( id, num[prime[i]], 1e9 );else addedge( num[prime[i]], id, 1e9 );while( val % prime[i] 0 ) val / prime[i];}
}int main() {sieve(); tot 1001;scanf( %d, T );while( T -- ) {memset( head, -1, sizeof( head ) ); cnt -1;scanf( %d %d, m, n );s 0, t n m 1;for( int i 1;i m;i ) scanf( %d, b[i] );for( int i 1;i n;i ) scanf( %d, r[i] );for( int i 1;i m;i ) divide( i, b[i] );for( int i 1;i n;i ) divide( i m, r[i] );for( int i 1;i m;i ) addedge( s, i, 1 );for( int i 1;i n;i ) addedge( i m, t, 1 );printf( %d\n, dinic() );}return 0;
}
