#UVa:11461-Square Numbers

先建表算出1~N有幾個square numbers,接著利用減法就可以算出a~b有幾個square numbers。

C=+(0.012)

/*******************************************************/
/* UVa 11461 Square Numbers                            */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2015/01/26                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int LIMIT = 100000;

int main(){
  int dp[LIMIT + 5] = {0};
  for( int i = 1 ; i * i <= LIMIT ; ++i ){
    ++dp[i*i];

    int limit = min(LIMIT, (i+1)*(i+1));
    for( int j = i * i + 1 ; j <= limit ; ++j ){
      dp[j] = dp[j-1];
    }
  }

  int a, b;
  while( scanf("%d%d", &a, &b) != EOF && (a != 0 || b != 0) ){
    printf("%d\n", dp[b] - dp[a-1]);
  }
  return 0;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料