louisfghbvc的部落格

題目大意:  問有多少個AXB+C = N

思路:  其實觀察一下測資，就發現先枚舉C之後，AB的因數有幾個。所以問題轉化為算因數的數量。用質數篩法，然後計算

比如12好了，怎麼找12的因數，首先12= 2^2 x 3^1，所以就是次方項+1 相乘， (2+1)*(1+1) = 6個。為甚麼呢。因為相當於2取0次~取2次，乘上3取0次或1次。

代碼:  

#include <bits/stdc++.h>
 
#define Fast cin.tie(0), ios::sync_with_stdio(0)
#define All(x) x.begin(), x.end()
#define louisfghbvc int t; cin >> t; while(t--)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
typedef vector<LL> vi;
 
template<typename T> istream& operator>>(istream &is, vector<T> &v) { for(auto &it : v) is >> it; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep = ""; for(const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void dbg_out() { cerr << " end.\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
 
const int N = 1e6+5;
vector<int> p;
bool np[N];
 
void init(){
    for(int i = 2; i <= sqrt(N); ++i){
        if(!np[i]){
            p.push_back(i);
            for(int j = 2*i; j < N; j+=i)
                np[j] = 1;
        }
    }
}
 
LL gg(int x){
    LL res = 1;
    for(int &prime: p){
        if(prime > x) break;
        LL c = 0;
        while(x%prime == 0){
            x /= prime;
            c++;
        }
        res *= (c+1);
    }
    if(x != 1) res *= 2;
    return res;
}
 
void solve(){
    init();
    int n;
    cin >> n;
    LL res = 0;
    for(int c = 1; c < n; ++c){
        int ab = n-c;
        res += gg(ab);
    }
    cout << res << "\n";
}
 
int main()
{
    Fast;
    //louisfghbvc{
        solve();
    //}
    return 0;
}