剪枝例题一道

例题一

Code force round
我的思路，DFS遍历所有x，y，然后用set记录所有k，但是TLE了，最后发现，可以应用剪枝，如果一个x，y得出的k已经在set中存在了，那么不用再继续DFS后续了。

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define For for(int i=1;i<=n;i++)
#define Whole(x) for(auto item:x)
const int N = 2e5;
set<int> ans;
int l,a,b;
void dfs(int sa,int sb){
    int k=l;
    k/=sa;k/=sb;
    if(ans.find(k!=ans.end())//这两行
    return;//是剪枝，避免重复DFS
    ans.emplace(k);
    if(k%a==0)
        dfs(sa*a,sb);
    if(k%b==0)
        dfs(sa,sb*b);
}
void inline solve() {
    cin>>a>>b>>l;
    ans.clear();
    dfs(1,1);
    cout<<ans.size()<<endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int num = 1;
    cin >> num;
    while (num--) {
        solve();
    }
    return 0;
}

还有暴力遍历法
令l/a=la l/b=lb(余数此处不显示0)
则遍历l除以的a的次数从0到la次，分别看能除以b几次，得到不同的x y组合，从而得到不同的k加入到set里面。

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
#define For for(int i=1;i<=n;i++)
#define rFor for(int i=n;i>0;i--)
#define Whole(x) for(auto item:x)
const int N = 2e5;

void inline solve() {
   int a,b,l;
   cin>>a>>b>>l;
   set<int> ans;
   while(1){
       int x=l;
       while(1){
           ans.emplace(x);
           if(x%b!=0){
               break;
           }
           x/=b;
       }
       if(l%a!=0){
           break;
       }
       l/=a;
   }
    cout<<ans.size()<<endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int num = 1;
    cin >> num;
    while (num--) {
        solve();
    }
    return 0;
}