剪枝例题一道

例题一

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>a>>b>>l;    ans.clear();    dfs(1,1);    cout 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;i0;i--)#define Whole(x) for(auto item:x)const int N = 2e5;void inline solve() {   int a,b,l;   cin>>a>>b>>l;   set 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 num;    while (num--) {        solve();    }    return 0;}