思路:先把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; //输出根节点的总方案数
}