fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. // 1回連分数展開して整数部分を返す
  5. // numerator / (sqrt(N) + denominator)
  6. // = 1 / (sqrt(23) - 4)
  7. // = 1 + 1 / (7 / (sqrt(23) - 3))
  8. // = ret + 1 / (numerator / (sqrt(N) + denominator))
  9. // ret : 返り値
  10. // numerator, denominator : in/out引数
  11. int expand(int N, int *numerator, int *denominator) {
  12.     int rep;
  13.  
  14.     *numerator = (N - *denominator * *denominator) / *numerator;
  15.     *denominator *= -1;
  16.     for( rep = 1;; rep++ ) {
  17.         *denominator -= *numerator;
  18.         if( N < (*numerator - *denominator) * (*numerator - *denominator) ) break;
  19.     }
  20.  
  21.     return rep;
  22. }
  23.  
  24. int isSquareNum(int n) {
  25.     int i;
  26.  
  27.     if( n == 0 ) return 1;
  28.  
  29.     for( i = 1; i * i <= n; i++ ) {
  30.         if( i * i == n ) return 1;
  31.     }
  32.  
  33.     return 0;
  34. }
  35.  
  36. int main(void) {
  37.     int N;
  38.     int cnt = 0;
  39.  
  40.     for( N = 2; N <= 10000; N++ ) {
  41.         int numerator = 1;
  42.         int denominator = 1;
  43.         int firstNume, firstDeno;
  44.         int i;
  45.  
  46.         if( isSquareNum(N) ) continue;
  47.  
  48.         //printf("[%d;(", (int)floor(sqrt((double)N)));
  49.         firstNume = numerator = 1;
  50.         firstDeno = denominator = -1 * (int)floor(sqrt((double)N));
  51.         for( i = 1;; i++ ) {
  52.             //printf("%d,", expand(N, &numerator, &denominator));
  53.             expand(N, &numerator, &denominator);
  54.             if( numerator == firstNume && denominator == firstDeno ) break;
  55.         }
  56.         //printf(")\n");
  57.  
  58.         if( i % 2 != 0 ) cnt++;
  59.     }
  60.  
  61.     printf("%d\n", cnt);
  62.  
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 2160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1322
https://ideone.com/xS6Sqg
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!