0729提高组3 - 数学

老师的博客：https://blog.nowcoder.net/n/f64ecade2ea446f1a200d21aa11564c1

示例1
输入
2
41 1 96 288
95 1 37 1776
输出
6
2
说明
第一组输入数据，x可以是9、18、36、72、144、288，共有6个。
第二组输入数据，x可以是48、1776，共有2个。

备注:
对于50%的数据，保证有1≤a0，b1，b0，b1≤10000且n≤100。
对于100%的数据，保证有1≤a0，b1，b0，b1≤2,000,000,000且n≤2000。

x*a0/gcd(x,a0)==a1
gcd(x,b0)==b1

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 45000; 
typedef pair<int,int>PII;

int prime[maxn],cnt;
bool st[maxn];

PII factor[50];
int cntf;

int divider[maxn],cntd;
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])prime[cnt++] = i;
        for(int j=0;prime[j] <= n/i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j]==0)break; 
        }
    }   
} 

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

void dfs(int u,int p)
{
    if(u>cntf)
    {
        divider[cntd++] = p;
        return ;
        
    }
    
    for(int i=0;i<=factor[u].second;i++)
    {
        dfs(u+1,p);
        p *= factor[u].first;
    }
}

int main()
{
    get_primes(maxn);
    
    int t,l,k,m,n;
    int tt;
    cin>>n;

    while(n--)
    {
        int a0,b0,a1,b1;
        cin>>a0>>a1>>b0>>b1;
        
        int d = b1;
        cntf = 0;
        for(int i=0;prime[i] <= d/prime[i];i++)
        {
            int p = prime[i];
            if(d%p == 0)
            {
                int s = 0;
                while( d%p == 0) s++,d/=p;
                
                factor[++cntf] = {
                    p,s
                };
            }
        }
        
        if(d > 1 )factor[++cntf] = {
                d,1
        };
        cntd = 0;
        dfs(1,1);
        
        int res = 0;
        for(int i = 0;i < cntd; i++)
        {
            int x = divider[i];
            if(gcd(x,a0) == a1 && (ll) x * b0 / gcd(x,b0) == b1)
            {
                res++;
            }
        }
        
        cout<<res<<endl;
    }
    

    return 0;
}

备注:
对于30%的数据，有0≤k≤10；
对于50%的数据，有a=1，b=1；
对于100%的数据，有0≤k≤1,000，0≤n,m≤k，且n+m=k，0≤a，b≤1,000,000。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 45000; 
const int mod  = 10007;

typedef pair<int,int>PII;
int pow(int a,int k)
{
    a %= mod;
    int res = 1;
    while(k)
    {
        if(k & 1)
        res = res * a %mod;
        a = a*a % mod;
        k >>= 1; 
    }
    return res;
    
}

int main()
{
    int a,b,k,n,m;
    cin>>a>>b>>k>>n>>m;
    int res = pow(a,n) * pow(b,m) %mod;
    for(int i=1,j=k;i<=n;i++,j--)
    {
        res = res * j % mod;
        res = res * pow(i,mod - 2)%mod;
    }
    cout<<res<<endl;

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2010; 

int cc[maxn][maxn];
int ss[maxn][maxn];

int c(int k)
{

    for(int i=0;i<maxn;i++)
        for(int j=0;j<=i;j++)
        {
            if(!j) cc[i][j] = 1 % k;
            else cc[i][j] = (cc[i-1][j] + cc[i-1][j-1]) % k;
            
            if(!cc[i][j]) ss[i][j] = 1;
        }

    for(int i=0 ; i < maxn ; i++)
        for(int j=0 ; j < maxn ; j++)
        {
            if(i) ss[i][j] += ss[i-1][j];
            if(j) ss[i][j] += ss[i][j-1];
            if(i && j) ss[i][j] -= ss[i-1][j-1];
        }
}
int main()
{
    int t,l,k,m,n;
    int tt;
    scanf("%d%d",&t,&k);

    c(k);

    while(t--)
    {
        scanf("%d%d",&n,&m);
        
        printf("%d\n",ss[n][m]);
    }
    

    return 0;
}

说明
小凯手中有面值为3和7的金币无数个，在不找零的前提下无法准确支付价值为 1、2、4、5、8、11的物品，其中最贵的物品价值为11。
比11贵的物品都能买到，比如：
12 = 3 x 4 + 7 x 0
13 = 3 x 2 + 7 x1
14 = 3 x 0 + 7 x 2
15 = 3 x 5 + 7 x 0

备注:
对于 30% 的数据：1 ≤ a,b ≤ 50;
对于 60% 的数据： 1 ≤ a,b ≤ 10,000;
对于 100% 的数据：1 ≤ a,b ≤ 1,000,000,000。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 100000+10 
int main()
{
    int t,l,r,m,n;
    int tt;
    scanf("%d%d",&m,&n);
        tt = m*n - ( m+n );
        printf("%I64d\n",tt);
    return 0;
}