المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۱۹:سوال ۲

اعداد اولوناچی

یک عدد «اولوناچی» اگر بر هیچ کدام از اعداد فیبوناچی بزرگ‌تر از یک بخش‌پذیر نباشد. برای مثال عدد ۷۷ اولوناچی است.

چند درصد اعداد شش رقمی اولوناچی است؟

اگر جواب این پرسش $F$ باشد (که $F$ یک عدد اعشاری بین صفر تا صد است)، مقدار $F\times \Delta$ را تا پنج رقم اعشار بنویسید.

پاسخ

‎
 
 
 
#include <iomanip> 
#include <iostream> 
#include <vector> 
using namespace std; 
 
const int MAX = 1000*1000; 
 
vector<int> fibo; 
 
int main() { 
  fibo.push_back(2); 
  fibo.push_back(3); 
  while (true) { 
    int n = fibo.size(); 
    int k = fibo[n-1] + fibo[n-2]; 
    if (k > MAX) break; 
    fibo.push_back(k); 
  }   
 
  int all = 0, good = 0; 
  for (int i=MAX/10; i<MAX; i++) { 
    all++; 
    for (int j=0; j<fibo.size() && fibo[j] <= i; j++) 
      if (i % fibo[j] == 0) 
        goto hell; 
    good++; 
  hell: ; 
  }   
 
  double d = double(good) / all * 100; 
  cerr << fixed << setprecision(10) << d << endl; 
 
  return 0; 
}

ابزار صفحه