首页 > 代码库 > CSU 1803 2016倍数
CSU 1803 2016倍数
#include <iostream> #include <vector> #include <cstring> #include <queue> #include <cmath> #include <cstdio> using namespace std; typedef long long ll; const int N=3e3+20; const int inf=2e8; //题意:给出n,m<=1e9,问有多少对(a,b) a<=n,b<=m 满足a*b为2016倍数 //a=2016p+r1,b=2016q+r2 -> a*b=2016^2*p*q+2016(pr2+qr1)+r1r2. 则a*b为2016倍数等价于r1r2为2016倍数 //r[i]为n以内余2016为i的数个数,枚举余数即可 ll n,m; ll r1[N],r2[N]; int main() { while(cin>>n>>m) { memset(r1,0,sizeof(r1)); memset(r2,0,sizeof(r2)); ll x=n/2016,y=m/2016;//余数有多少组 ll p1=n%2016,p2=m%2016; for(int i=0;i<2016;i++) r1[i]+=x,r2[i]+=y; for(int i=1;i<=p1;i++) r1[i]++; for(int i=1;i<=p2;i++) r2[i]++; ll ans=0; for(int i=0;i<2016;i++) { for(int j=0;j<2016;j++) { if((i*j)%2016==0) ans+=r1[i]*r2[j]; } } cout<<ans<<endl; } return 0; }
CSU 1803 2016倍数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。