ZOJ 3326 An Awful Problem (較清晰寫法，附詳細注解)

ZOJ 3326 An Awful Problem (較清晰寫法，附詳細注解)

In order to encourage Hiqivenfin to study math, his mother gave him a sweet candy when the day of the month was a prime number. Hiqivenfin was happy with that. But several days later, his mother modified the rule so that he could get a candy only when the day of the month was a prime number and the month was also a prime number. He felt a bit upset because he could get fewer candies. What's worse, his mother changed the rule again and he had to answer a question before he could get a candy in those days. The question was that how many candies he could get in the given time interval. Hiqivenfin wanted to cry and asked you for help. He promised to give you half of a candy if you could help him to solve this problem.

Input

There are multiple test cases. The first line of input is an integer T (0 < T <= 50), indicating the number of test cases. Then T test cases follow. The i-th line of the next T lines contains two dates, the day interval of the question. The format of the date is yyyy mm dd. You can assume both dates are valid. Hiqivenfin was born at 1000-01-01 and would not die after 2999-12-31, so the queries are all in this interval.

Hiqivenfin didn't seem to be an earthman, but the calendar was the same as that we usually use. That is to say, you need to identify leap years, where February has 29 days. In the Gregorian calendar, leap years occur in years exactly divisible by four. So, 1993, 1994, and 1995 are not leap years, while 1992 and 1996 are leap years. Additionally, the years ending with 00 are leap years only if they are divisible by 400. So, 1700, 1800, 1900, 2100, and 2200 are not leap years, while 1600, 2000, and 2400 are leap years.

Output

Output the number of candies Hiqivenfin could get in the time interval. Both sides of the interval are inclusive.

Sample Input

2
1000 01 01 1000 01 31
2000 02 01 2000 03 01

Sample Output

0
10

題意：

求兩個日期間，月份是素數，天也是素數的日子有多少天。

解題：

比較煩的模擬題，但寫多了也就有套路了。分年份相同和不同兩種處理。相同則先分別處理兩個零頭月，然後模擬中間月份。不同則分別先處理兩個零頭年，然後模擬中間完整年份。其實年份之間可以每400年一個周期，找到第一個400年，然後直接計算，不過數據量比較小，沒有必要這樣處理。

代碼：

#include
using namespace std;
//是不是素數 
bool prime[32]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1};
//每個月份多少天 
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//判斷是不是閏年 
bool is_leapyear(int y)
{
	if((y%4==0&&y%100!=0)||y%400==0)return true;
	else return false;
}
int main()
{
    int t,y1,y2,m1,m2,d1,d2,cnt;
    cin>>t;
    while(t--)
    {
    	cnt=0;
    	cin>>y1>>m1>>d1>>y2>>m2>>d2;
    	//同一年 
    	if(y1==y2)
    	{
    		//同一月份 
	    	if(m1==m2)
	    	{
	    		if(prime[m1])
	    		{
				  for(int i=d1;i<=d2;i++)
	    		  {
		    		if(prime[i])
		    		cnt++;
	    		  }
	    		}
	    	}
	    	//不同月份 
	    	else
	    	{
	    		//如果是閏年，不管2月是不是用到，直接改成29天，減少分支判斷 
	    		if(is_leapyear(y1))month[2]=29;
	    		//處理零頭月份 
	    		if(prime[m1])
	    		{
                   for(int i=d1;i<=month[m1];i++)
                   {
                   	 if(prime[i])cnt++;
                   }
		    	}
		    	if(prime[m2])
		    	{
	    			for(int i=1;i<=d2;i++)
	    			{
			    		if(prime[i])cnt++;
			    	}
	    		}
	    		for(int i=m1+1;i<=m2-1;i++)
	    		{
	    			//是素數月才判斷 
	    			if(prime[i])
	    			{
		    		  for(int j=1;j<=month[i];j++)
		    		  if(prime[j])cnt++;
	    			}
		    	}
		    	//記得將2月重新改回28天 
		    	month[2]=28;
	    	}
	    }
	    //起始不同年份 
	    else
	    {
	    	//2月特殊處理 
    		if(is_leapyear(y1))month[2]=29;
    		//處理起始年
			//處理零頭月 
    		if(prime[m1])
    		{
		    	for(int i=d1;i<=month[m1];i++)
		    	if(prime[i])cnt++;
		    }
		    //處理其他月份 
		    for(int i=m1+1;i<=12;i++)
		    {
		    	if(prime[i])
		    	{
    			  for(int j=1;j<=month[i];j++)
    			  {
			    	if(prime[j])cnt++;
			      }
		    	}
    		}
    		month[2]=28;
    		//處理終止年 
    		//處理零頭月 
    		if(is_leapyear(y2))month[2]=29;
    		if(prime[m2])
    		{
		    	for(int i=1;i<=d2;i++)
		    	{
	    			if(prime[i])cnt++;
	    		}
		    }
		    //處理其他月份 
		    for(int i=1;i<=m2-1;i++)
		    {
    			if(prime[i])
    			{
			    	for(int j=1;j<=month[i];j++)
			    	{
	    				if(prime[j])cnt++;
	    			}
			    }
    		}
    		month[2]=28;
    		//中間完整年份處理 
    		for(int i=y1+1;i<=y2-1;i++)
    		{
    			//閏年53天，平年52天 
		    	if(is_leapyear(i))
		    	cnt+=53;
		    	else cnt+=52;
		    }
    	}
    	cout<