牛客周赛30

思路：先把x, y除以最大公约数变成最小值，然后同时乘以倍数cnt，只记录两个数都在[l,r]间的倍数。

代码：

int gcd(int a,int b){
	return b ? gcd(b, a % b) : a;
}
 
void solve(){
	int x, y, l, r;
	cin >> x >> y >> l >> r;
	int g = gcd(x, y);
	x /= g,y /= g;
	int ans = 0, cnt = 1;
    while(x * cnt < l || y * cnt < l)
        cnt ++;
	while(x * cnt <= r && y * cnt <= r)
		ans ++, cnt++;
	cout << ans << endl;
}

思路：从下往上dfs，树形dp；

代码：

int n;
vector<int>e[200010];
int f[200010][2];//0 1分别代表红，不染红
 
void dfs(int u,int fa){
	int m1 = 1, m2 = 1;
	for(auto v:e[u]){
		if(v == fa)continue;
		dfs(v, u);
		m1 = (m1 * (f[v][0])) % mod;      //u节点不染红的话，就需要每个子节点都染红
		m2 = (m2 * (f[v][0] + f[v][1]))%mod;  //u节点染红的话，子节点染不染红都可以
	}
	f[u][0] = m2;        //u节点染红的方案数
	f[u][1] = m1;        //u节点不染红的方案数
}
 
void solve(){
	cin >> n;
	for(int i = 1;i < n;i ++){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	cout <<(f[1][0] + f[1][1])%mod;      //输出根节点的总方案数
}