csu 1803 16年湖南省赛

2024-02-13 17:08

文章标签 16 1803 湖南省 csu

本文主要是介绍csu 1803 16年湖南省赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1803: 2016

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 628 Solved: 413
[ Submit][ Status][ Web Board]

Description

给出正整数 n 和 m，统计满足以下条件的正整数对 (a,b) 的数量：

1. 1≤a≤n,1≤b≤m;

2. a×b 是 2016 的倍数。

Input

输入包含不超过 30 组数据。

每组数据包含两个整数 n,m (1≤n,m≤10 ⁹).

Output

对于每组数据，输出一个整数表示满足条件的数量。

Sample Input

32 63
2016 2016
1000000000 1000000000

Sample Output

1
30576
7523146895502644

题意：

求a*b%2016==0的（a，b）数对的个数

题解：

同余求模定理：

同余定理具有可加、可减、可乘、乘方性：

(A + B) % C = (A % C + B % C) % C;

(A - B) % C = (A % C - B % C) % C;

(A * B) % C = (A % C * B % C) % C;

(A ^ B) % C = (A^N + B^N) % C;

由上面知道

(A * B) % C = (A % C * B % C) % C;

若满足题意，则有三种情况：

第一种：A%2016==0

第二种：B%2016==0

第三种：A%2016==0&&B%2016==0

三种情况肯定不好求

那就反过来求当(A * B) % C != 0的时候

得到 a = A%2016！=0

和 b = B%2016！=0

且（a*b）%2016！=0

然后就很好求了，统计两个区间【1，2016】，【1，2016】中数字出现的次数（每个数字经过模2016后）

即【1，a】中每个数字模2016后，统计【1，2016】中数字出现的次数

最后再计算（a*b）%2016！=0 的时候，a，b出现的次数相乘就好了

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define mem(a) memset(a,0,sizeof(a))
#define LL long long
#define mod 2016
LL arr1[2020],arr2[2020];int main()
{LL a,b;LL ans=0;//freopen("in.txt","r",stdin);while(scanf("%lld%lld",&a,&b)!=EOF){mem(arr1),mem(arr2);ans=a*b;LL temp1=a%mod,num1=a/mod;LL temp2=b%mod,num2=b/mod;for(int i=1;i<=2016;i++){arr1[i]=num1;arr2[i]=num2;}for(int i=1;i<=temp1;i++)arr1[i]++;for(int i=1;i<=temp2;i++)arr2[i]++;for(int i=1;i<=mod;i++)for(int j=1;j<=mod;j++)if(i*j%mod)ans-=arr1[i]*arr2[j];printf("%lld\n",ans);}return 0;
}

精简代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define  LL long longint main()
{int n,m;//freopen("in.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){LL ans=(LL)n*m;for(int i=1;i<=min(2016,n);i++)for(int j=1;j<=min(2016,m);j++)if(i*j%2016!=0)ans-=(LL)((n-i)/2016+1)*((LL)(m-j)/2016+1);printf("%lld\n",ans);}return 0;
}

这篇关于csu 1803 16年湖南省赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！