国内建站公司,中文wordpress实例,网站程序怎么上传,想学编程做网站在ACM生涯里已经预见两回判断这种方程是否有解、有几个解的问题了。
例如#xff1a;
1
给定非负整数a,b,c,n#xff0c;请判断axbyczn是否存在(x,y,z)均为非负整数的解
题目链接#xff1a;http://oj.xjtuacm.com/contest/14/problem/124/
再例如#xff1a; 2 现有…在ACM生涯里已经预见两回判断这种方程是否有解、有几个解的问题了。
例如
1
给定非负整数a,b,c,n请判断axbyczn是否存在(x,y,z)均为非负整数的解
题目链接http://oj.xjtuacm.com/contest/14/problem/124/
再例如 2 现有方程A1 * X1 A2 * X2 ... An * Xn P A1, A2, ... , An为变量X1, X2, ... , Xn的系数 给定P的取值范围求有多少个P使得方程存在非负整数解 题目链接http://oj.xjtuacm.com/contest/14/problem/124/ 而这种方程看似是数论问题往往能通过建模的方法转换成为图论里面最短路问题很奇妙对吧
我们就拿题目2来说设所有的给出的并且满足这个方程的P值如果我们把P值对Ai进行取模,得到的数必然存在于Ai的剩余系中也就是说
P%Ai 在区间[0,Ai-1]里面乍一看我们这样做岂不是把信息减损了P映射到[0,Ai-1]相当于把模数相同的P都给去冲了。不用担心我们有神奇的办法可以从剩余系[0,Ai-1]
中把所有的P无损的还原回来。
那么怎么做呢
假设我们已经有了所有满足
(A1 * X1 A2 * X2 ... An * Xn)%Ai P%(Ai) y
的y值那么我们将y不断地增加Ai然后判断得到的值是否在[Pmin,Pmax]是不是就可以得到所有的P值了呢。哇真的很奇妙
举个例子来说
我们选取Ai等于5
Pmin 0Pmax 11其中一个y 2
那么225 7就是满足条件的所有P%Ai 2意义下
但是这里是有一个坑点的细心的朋友可以发现我上面举得那个例子实际上是错误的因为这样扩展y的方法会造成P的数量比真实情况下要多。
这样理解
假设满足mod Ai 2意义下的P只有7的话那么根据上面的方法将会的得到一个假的P(P 2)相当于无形之间把答案的数量增多了。
这就要求我们保存一个最小的P(mod Ai 2)在最小的这个P的基础上开始扩展而不是从2的基础上开始扩展就可以保证答案的正确性了。
由于这个Ai是可以随便取得但是取最小的那个是最好的因为取最小的那个Ai剩余系是最小的我们记A min{Ai}
这样我们的问题就转化成为求所有对应A的剩余系中值的最小P求出来这个以后直接进行扩展就好了。
而要求这样的P我们就可以采用最短路的做法具体怎么做呢
我们把点定义成为剩余系中的值把边定义成为一个剩余系中的值向另一个剩余系中的值转移所需要的代价。
很明显的d[0] 0
然后从i出发向(iAk)%A这个点进行转移的边的代价为Ai
也就是说我们可以把i和(iAk)做一条边权位Ak得边
图建好以后做一个dijkstra就好了
得到的d[i]就是对应剩余系中的i的P的最小值。 第一题和第二题是基本相同的这里就不赘述了值得一提的是第一题还可以用扩展欧几里得来做
代码
第一题最短路建模的方法 #include iostream
#include queue
#include cstdio
#include cstring
#include algorithm
using namespace std;
int a,b,c;
long long n;
const int MAXN 3e5;
const int V_MAXN 2e5;
const long long INF 1e18;
int N,X,Y,MAX;
int head[V_MAXN];
struct edge{ int v; int next; int cost;
}Es[MAXN1];
long long d[MAXN];
int cnt;
typedef pairint,int P; void dijkstra(int x){ for(int i 0;i MAXN;i) d[i] INF; d[x] 0; priority_queueP,vectorP,greaterP que; que.push(P(0,x)); while(!que.empty()){ P p que.top();que.pop(); int dis p.first; int v p.second; if(d[v] dis) continue; //for(int i 0;i 2*N2;i){ for(int e head[v];e! -1;e Es[e].next){ int cost Es[e].cost; int i Es[e].v; if(cost d[v] d[i]){ d[i] d[v] cost; que.push(P(d[i],i)); } } }
}
inline void add_edge(int i,int j,int cost){ //G[i][j] cost; Es[cnt].v j; Es[cnt].cost cost; Es[cnt].next head[i]; head[i] cnt;
}
void init(){ cnt 0; memset(head,-1,sizeof(head));
}
int main(){int cas 0;while(~scanf(%d%d%d%lld,a,b,c,n)){init();int p min(a,b);p min(p,c);for(int i 0;i p;i){add_edge(i,(ia)%p,a);add_edge(i,(ib)%p,b);add_edge(i,(ic)%p,c);}dijkstra(0);for(int i 0;i p;i){if(d[i] n){if((n - d[i])%p 0){printf(Case #%d: Yes\n,cas);goto ns;}}}printf(Case #%d: No\n,cas);ns:;} return 0;
}第一题扩展欧几里得地方法 #include iostream
#include cstdio
#include algorithm
using namespace std;
typedef long long int LL;
LL extgcd(LL a,LL b,LL x,LL y)
{LL d a;if(b ! 0){d extgcd(b,a%b,y,x);y - (a/b)*x;}else{x 1;y 0;}return d;
}
void solve(){LL k[3],n;int cas 0;while(~scanf(%lld%lld%lld%lld,k[0],k[1],k[2],n)){sort(k,k3);LL limit min(n/k[2],k[0]);int f 0;if(n%k[2] ! 0)for(int i 0;i limit;i){LL x,y;LL res n - (LL)i*k[2];LL d extgcd(k[0],k[1],x,y);if(res % d ! 0){continue;}else{if(x 0 y 0){f 1;break;}else {if(y 0){swap(x,y);swap(k[0],k[1]);} LL r (res%k[1])*(-x)%k[1];if(r 0){f 1;break;}else{//coutdouble(n)endl;if(res 1000000){if(res/k[0]*y res/k[1]*(-x)){f 1;break;}}elseif(res*y/k[0] res*(-x)/k[1]1){f 1;break;}}}}}else{f 1;}printf(Case #%d: ,cas);if(f){puts(Yes);}else{puts(No);}}
}
int main(){solve();return 0;
}第二题最短路建模的方法 #include iostream
#include cstdio
#include vector
#include algorithm
#include queue
#include cstring
using namespace std;
#define int long long
const int MAXN 1e7;
const int V_MAXN 1e7;
const int INF 1e18;
int N,X,Y,MAX;
int head[V_MAXN];
struct edge{ int v; int next; int cost;
}Es[MAXN1];
int d[MAXN];
int cnt;
typedef pairint,int P; void dijkstra(int x){ for(int i 0;i MAXN;i) d[i] INF; d[x] 0; priority_queueP,vectorP,greaterP que; que.push(P(0,x)); while(!que.empty()){ P p que.top();que.pop(); int dis p.first; int v p.second; if(d[v] dis) continue; //for(int i 0;i 2*N2;i){ for(int e head[v];e! -1;e Es[e].next){ int cost Es[e].cost; int i Es[e].v; if(cost d[v] d[i]){ d[i] d[v] cost; que.push(P(d[i],i)); } } }
}
inline void add_edge(int i,int j,int cost){ //G[i][j] cost; Es[cnt].v j; Es[cnt].cost cost; Es[cnt].next head[i]; head[i] cnt;
}
void init(){ cnt 0; memset(head,-1,sizeof(head));
}
int n;
long long Pmin,Pmax;
int A[20];
main(){while(scanf(%lld%lld%lld,n,Pmin,Pmax) ! EOF){init();int p INF;for(int i 1;i n;i){scanf(%lld,A[i]);if(A[i])p min(p,A[i]);}if(p INF) {puts(Pmin 0?1:0);continue;}for(int i 0 ;i p;i){for(int j 1;j n;j){add_edge(i,(i A[j])%p,A[j]);}}dijkstra(0);long long ans 0;for(int i 0;i p;i){if(d[i] INF){long long l,r; if(d[i] Pmin) {l (Pmin - 1 - d[i])/p 1;}else{l 0;}if(d[i] Pmax){r (Pmax - d[i])/p 1; } else{r 0;}ans r - l;}}printf(%lld\n,ans);}return 0;
}
