Magic Forest

The first line contains two integer N₀ and M(1≤N₀,M≤10³), the number of trees you initially know and the number of queries.
The next line are N₀ integer a₁,…,a_n (1≤a_i≤10⁵) as described above.
Then followed M lines with each line a integer X(1≤X≤10⁵) as described above.

For each query:
If there is no such a tree print “NO”.
Otherwise find a solution that X=∑a_i×k_i and print N integer k_i, which should be no greater than 64-bits integer in a line. If there are multiple solutions, print any of them.
Warning: do not print extra space or empty line!

C++14(g++5.4) 解法, 执行用时: 131ms, 内存消耗: 2380K, 提交时间: 2019-02-17 09:58:17

#include<stdio.h>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
int n,m;
long long a[1100],x,d,b[1100],y;
inline void ext_gcd(long long a,long long b,long long &d,long long &x,long long &y){
	if (!b){
		d=a;x=1;y=0;
		return;
	}
	ext_gcd(b,a%b,d,y,x);
	y-=a/b*x;
}
inline void wor(int now){
	ext_gcd(d,a[now],d,x,y);
	b[now]=y;
	fo(i,1,now-1) b[i]*=x;
}
int main(){
	scanf("%d%d",&n,&m);
	fo(i,1,n) scanf("%lld",&a[i]);
//	std::sort(a+1,a+n+1);
	b[1]=1;d=a[1];
	fo(i,2,n) wor(i);
	while (m--){
		scanf("%lld",&x);
		if (x%d==0){
			x/=d;
			fo(i,1,n-1) printf("%lld ",b[i]*x);
			printf("%lld\n",b[n]*x);
		}else printf("NO\n");
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 99ms, 内存消耗: 2408K, 提交时间: 2023-03-03 21:35:32

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],b[N],x,y,d;
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int x1,y1,gcd;
	gcd=exgcd(b,a%b,x1,y1);
	x=y1,y=x1-a/b*y1;
	return gcd;
} 
void js(int lx){
	d=exgcd(d,a[lx],x,y);
	b[lx]=y;
	for(int i=0;i<lx;i++){
		b[i]*=x;
	}
}
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	b[0]=1;
	d=a[0];
	for(int i=1;i<n;i++){
		js(i);
	}
	while(m--){
		int op;
		cin>>op;
		x=op%d;
		if(x){
			cout<<"NO\n";
		}	
		else {
			x=op/d;
			for(int i=0;i<n;i++){
				cout<<b[i]*x<<" ";
			}
			cout<<"\n";
		}
	}
}

详情