题目大意:求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。
题目解析:X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。可以写成(X-b[0])/a[0]==0;(X-b[1])/a[1]==0;(X-b[2])/a[2]==0;
(X-b[3])/a[3]==0;...........即X-b[i]时a[i]数组的最小公倍数Lcm;所以可以把N分成k段,N=k*Lcm+R;在每R到R+lcm中都有最多有一个数满足题意;然后再遍历0----R上是否存在这这样的X满足题目要求(最多有一个);
#include<stdio.h> #include<stdlib.h> int Gcd( int a, int b )//求最大公约数 { b==0?a:Gcd( b, a%b ); } int Lcm(int a,int b)//求最小公倍数 { return (a/Gcd(a,b)*b); } int sover( int a[], int b[], int n, int sum, int N ) { int count=0; int t=N%sum,i,j;//t为N模最小公倍数sum的余数; for( i=t+1;i<=sum+t;i++ )//在段上遍历查找满足条件的数, { for( j=0; j<n; j++ ) { if( i%a[j]!=b[j] ) break; } if( j>=n )//若找到,则在每段k*sum+t到(k+1)*sum+t上都有这样的数存在; { count+=N/sum; break; } } for( i=1;i<=t; i++ )//再在1到t上遍历查找是否有满足条件的数; { for( j=0; j<n; j++ ) { if( i%a[j]!=b[j] ) break; } if( j>=n ) { count++;//有就加一; break; } } return count; } int main( ) { int a[10],b[10]; int n,T,N; scanf( "%d",&T ); while( T-- ) { int sum=1; scanf( "%d%d",&N, &n ); for( int i=0; i<n; i++ ) { scanf( "%d",&a[i] ); sum=Lcm(sum,a[i]); } for( int i=0; i<n; i++ ) scanf( "%d",&b[i] ); printf( "%d\n",sover( a,b,n,sum,N ) ); } return 0; }
HDU1370Biorhythms(简单的中国剩余定理)
题目意思:有3个循环周期,周期天数分别为23、28、33。对于某一年,已知某年这3个周期的某一峰值分别是当年的第p、e、i天,问从第d天开始到最近一个满足3个周期都达到峰值的日期还有多少天。
题目解析:题目21252不大,可以用暴力打表法;
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<cstdlib> using namespace std; #define MAX 21252 int temp[35][35][35]={0}; void init()//打表;中国剩余定理 { for(int i=0;i<=MAX;i++) temp[i%23][i%28][i%33]=i; } int non(int ans) { if(ans<=0)return ans+21252;//非负; return ans; } int main() { init(); int t; int p,e,i,d; scanf("%d",&t); while(t--) { int count=0; while(1) { scanf("%d%d%d%d",&p,&e,&i,&d); if(p==-1&&e==-1&&i==-1&&d==-1)break; printf("Case %d: the next triple peak occurs in %d days.\n",++count,non(temp[p%23][e%28][i%33]-d)); } } return 0; }