数论模运算调整方法及Project Euler第19题解法合理性求证

Hey there! Let's work through your questions about Problem 19 step by step—no confusing jargon, promise.

Is your answer of 171 correct? #

Great news first: yes, 171 is the correct answer for Project Euler Problem 19! The problem asks for the number of months between 1901 and 2000 where the first day is a Sunday, and that exact count checks out. So your solution is on the right track—nice work!

Making sense of modulo operations here #

I get it, modulo can feel tricky at first, but it’s perfect for this problem because we’re dealing with a 7-day weekly cycle. Here’s how it works in plain terms:

• Every time we add days to our current date, we only care about how those days shift the day of the week—not the total number of days. Since there are 7 days in a week, any multiple of 7 days just loops back to the same weekday.
• For example: If January has 31 days, 31 divided by 7 leaves a remainder of 3 (because 7*4=28, 31-28=3). That means if January 1 is Monday, February 1 will be 3 days later—Thursday. Using modulo, we calculate this as (current_weekday + 31) % 7 to get the new weekday.
• The key idea: Modulo 7 gives us the "offset" from the starting weekday, so we never have to track huge numbers of days—just the remainder that matters for the weekly cycle.

Fixing the hash map when using 0 for Monday #

The issue with mapping 0 to Monday usually comes from mixing up the weekday numbering and how we count offsets. Let’s clear this up:

1. First, define your numbering clearly:

   weekday_map = {
       0: "Monday",
       1: "Tuesday",
       2: "Wednesday",
       3: "Thursday",
       4: "Friday",
       5: "Saturday",
       6: "Sunday"
   }
   

2. Start with the known value: 1900-01-01 is Monday, so that’s current_weekday = 0.
3. Calculate the shift for each month: For each month’s day count, update current_weekday = (current_weekday + days_in_month) % 7. This gives you the first day of the next month.
4. Remember to start counting from 1901! 1900 is just the starting point to get to 1901-01-01’s weekday. Once you’re in 1901, every time current_weekday == 6 (since 6 maps to Sunday), increment your count.

The mistake people often make is either misaligning the number-to-weekday mapping or forgetting to skip the 1900 calendar year in their final count. Double-check those two things, and your 0-based mapping should work perfectly.

内容的提问来源于stack exchange，提问作者Patrick Olila