设为首页 加入收藏

TOP

Gym100920J
2019-04-03 22:08:04 】 浏览:54
Tags:Gym100920J

求Ax+By<=C,非负整数对(x,y)的个数

首先令y=0;则x<=(C/A);ans=(C/A)+1;

将Ax+By=C反转之后利用类欧几里得算法:f(a,b,c,n)=∑((a*i+b)/c) (0<=i<=n);求解

反转之后,a=A,b=C%A,c=b,n=C/A;

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define bug printf("bug\n");
#define N 1000005
#define pb emplace_back
#define fi first
#define se second
#define sc scanf
#define pf printf
#define Endl '\n'
using namespace std;
const ll inf=1e18;
const ll mod=1000000007;
ll qm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }
    return (ans%mod+mod)%mod;
}
ll cal(ll a,ll b,ll c,ll n){
    if(a==0)
 
			
color: #0000ff;">return
(b/c)*(n+1); if(a>=c||b>=c)return cal(a%c,b%c,c,n)+n*(n+1)*(a/c)/2+(b/c)*(n+1); ll m=(a*n+b)/c; return n*m-cal(c,c-b-1,a,m-1); } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll a,b,c; cin>>a>>b>>c; cout<<cal(a,c%a,b,c/a)+c/a+1<<endl; return 0; }

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇this指针详解 下一篇C++编程笔记丨世界上最简单的无锁..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }