This problem follows directly from problem 60 and is labeled as having a 20% difficulty level, but in my case, I didn’t find it particularly hard to solve.
To tackle problems involving n-gonal numbers, it’s generally effective to focus on correctly checking whether a number satisfies the condition of being an n-gonal number. That approach should be sufficient without much difficulty.
In this problem, you’re asked to find a cyclic sequence of six 4-digit numbers, each one being a different type of polygonal number—specifically, a triangle (3-gonal), square (4-gonal), …, up to an octagonal (8-gonal) number—where the numbers are connected by their last two and first two digits.
The strategy is to first generate all 4-digit 3-gonal numbers. Then, for each one, you find a 4-gonal number that starts with the last two digits of the 3-gonal number. You continue this process, chaining the numbers together, aiming to finally return to a number that links back to the original 3-gonal number—thus forming a cycle.
In my case, I precomputed all the relevant polygonal numbers for n from 3 to 8 and then wrote code to test whether the numbers could form such a cyclic sequence. In fact, there aren’t that many 4-digit n-gonal numbers. Since each polygonal number can be represented by a quadratic formula, their values grow rapidly, which limits the total count.
//------------------------------------------------
// Project Euler #61 - Cyclical Figurate Numbers
// - by Aubrey Choi
// - created at 2015-04-09
//------------------------------------------------
#include <stdio.h>
#include <math.h>
int cyclic(int bitflag, int start, int end, int sum);
int polygonal[6][1000];
int pcount[6] = { 0, 0, 0, 0, 0, 0 };
int main()
{
int pdiff[6] = { 1, 1, 1, 1, 1, 1 };
int pdiff2[6] = { 1, 2, 3, 4, 5, 6 };
for( int i = 0 ; i < 6 ; i++ )
{
int s = 0;
for( int n = 0 ; ; n++, pdiff[i] += pdiff2[i] )
{
s += pdiff[i];
if( s < 1000 ) continue;
if( s >= 10000 ) break;
if( s%100 < 10 ) continue;
polygonal[i][pcount[i]++] = s;
}
printf("%d : %d\n", i, pcount[i]);
}
for( int i = 0 ; i < pcount[0] ; i++ )
{
int c = polygonal[0][i];
int ans = cyclic(1, c%100, c/100, c);
if( ans ) printf("Ans = %d\n", ans);
}
}
int cyclic(int bitflag, int start, int end, int sum)
{
if( bitflag == 0x3f )
{
if( start == end ) return sum;
return 0;
}
for( int i = 1 ; i < 6 ; i++ )
{
if( (bitflag>>i)&1 ) continue;
for( int j = 0 ; j < pcount[i] ; j++ )
{
int c = polygonal[i][j];
if( c/100 == start )
{
int ans = cyclic(bitflag|(1<<i), c%100, end, sum+c);
if( ans ) return ans;
}
}
}
return 0;
}
'Programming > Project Euler' 카테고리의 다른 글
[C/C++] Project Euler #63 - Powerful digit counts (2) | 2025.05.17 |
---|---|
[C++] Project Euler #62 - Cubic Permutations (2) | 2025.05.17 |
[C/C++] Project Euler #60 - Prime Pair Sets (2) | 2025.05.11 |
[C/C++] Project Euler #59 - XOR Decryption (0) | 2025.05.09 |
[C++] Project Euler #58 - Spiral Primes (0) | 2025.05.08 |