Sgu/491

题目是说给一个N。让你求有多少对A和B，让方程 Ax+By=N有自然数解。。 首先算出所有小于N的数的因子，一个数的因子个数是 logn级别的。 总共就是NlogN. 先枚举A再枚举x。。然后算出所有可能的B。。然后对于每个A去一次重。。 将所有答案加起来就可以了。。 过的人那么少是因为很多人都错估了暴力枚举的复杂度，是n*logn*logn的。。 Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<ctime>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100000+1;int n;
vector<int> A[maxn];
typedef vector<int>::iterator it;
typedef vector<int>::reverse_iterator rit;
typedef long long ll;
void Cal(int x)
{
    static int tmp[10000];
    int cnt=0;
    for(int i=1;i*i<=x;i++)if(x%i==0)
        tmp[cnt++]=i,tmp[cnt++]=x/i;
    sort(tmp,tmp+cnt);A[x].push_back(tmp[0]);
    for(int j=1;j<cnt;j++)
        if(tmp[j]!=tmp[j-1])
            A[x].push_back(tmp[j]);
}
int Ans[maxn*50];
int main()
{
    //freopen("in","r",stdin);
    int o=clock();
    cin>>n;
    for(int i=1;i<n;i++) Cal(i);
    int ans=0;
    for(int a=1;a<n;a++)
    {
        int*end=Ans;
        for(int l=a;l<n;l+=a)
        {
            int r=n-l;
            for(rit i=A[r].rbegin();i!=A[r].rend();i++)
                if(*i>a) *(end++)=*i;
                else break;
        }
        if(Ans==end) continue;
        sort(Ans,end);
        ans++;
        for(int*i=Ans+1;i!=end;i++)
            if(*i!=*(i-1)) ans++;
    }
    cout<<ans<<endl;
}