2019牛客国庆集训派对day7 A 2016（同余取模）

分手后的思念是犯贱 2023-06-05 08:48 5阅读 0赞

[A.2016][]

题目描述

给出正整数 n 和 m，统计满足以下条件的正整数对 (a, b) 的数量：  
1.1≤a≤n,1≤b≤m  
2.a×b 是 2016 的倍数。

输入描述:  
输入包含不超过 30 组数据。  
每组数据包含两个整数 n, m (1≤n,m≤109).  
输出描述:  
对于每组数据，输出一个整数表示满足条件的数量。

示例1  
输入  
32 63  
输出  
1

示例2  
输入  
2016 2016

输出  
30576

示例3  
输入  
1000000000 1000000000

输出  
7523146895502644

之前做过一个一样的题，那个数是2017  
[G.2017][]  
因为2017是一个质数。所以找两个区间2017的倍数即可。  
两个数可以得到2016的组合好多  
【1，2016】 【2，1008】【4，504】…  
不能找2016的倍数，这样做会少。

那我们就找两个区间最大值模除2016的乘积，如果是乘积为2016，这个数就满足。  
分析：  
a%2016=a1 ; b%2016=b1  
求a \* b =2016 \* k  
如果a1 \* b1%2016==0 满足a \* b=2016 \* k

证明：a1=a%2016 ; b1=b%2016  
a1 \* b1 %2016=( a%2016 \* b%2016 ) %2016 =a \* b %2016

这样我们就把一个范围很大的数缩小到2016之内了

统计n，m%2016 每个数的个数

暴力寻找乘积%2016==0 加起来就行了

#include<iostream>
    #include<cstring>
    #include<algorithm> 
    using namespace std;
    typedef long long ll;
    const int maxn=2020;
    ll a[maxn],b[maxn];
    int main()
    { 
    	ll n,m;
    	while(cin>>n>>m)
    	{ 
    		memset(a,0,sizeof(a));
    		memset(b,0,sizeof(b));
    		ll num;
    		num=n/2016;
    		for(int i=1;i<=2016;i++)
    		{ 
    			a[i]=num;
    		}
    		for(int i=1;i<=n%2016;i++)
    		{ 
    			a[i]++;
    		}
    		
    		num=m/2016;
    		for(int i=1;i<=2016;i++)
    		{ 
    			b[i]=num;
    		}
    		for(int i=1;i<=m%2016;i++)
    		{ 
    			b[i]++;
    		}
    		ll ans=0;
    		for(int i=1;i<=2016;i++)
    		{ 
    			for(int j=1;j<=2016;j++)
    			{ 
    				if((i*j)%2016==0)
    					ans+=a[i]*b[j];
    			}
    		}
    		
    		cout<<ans<<endl;
    	}
    	return 0;
    }

[A.2016]: https://ac.nowcoder.com/acm/contest/1112/A
[G.2017]: https://blog.csdn.net/weixin_43667611/article/details/102212434