1776: Press the switch
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 447 Solved: 116
[Submit][Status][Web Board]
Description

達達的家里有一串長度為n的燈泡，編號1,2,3,4…n-1,n。每一個燈泡都有一個開關，達達每次選一個數a，把編號為a的倍數的燈泡的開關都按一遍。

假定燈剛開始都開著，他做了m次這樣的事，問他爸媽打他沒有？偶，不不不，問最后有幾個燈開著。

Input

多組測試數據，第一行輸入一個n（1<=n<=1e12）

第二行數輸入一個數m（0<=m<=2）

接下來輸入m個數ai（1<=ai<=min(1000,n)）

Output

輸出最后結果

Sample Input

100
1
2
5
2
2 3
100000000000
1
1

Sample Output

50
2
0

HINT

Source
AC_code:
//思維要縝密

#include <iostream> using namespace std; int gcd(int a,int b)//求a，b最大公約數 {return b?gcd(b,a%b):a; } int main() {long long n;while(cin>>n){int m;cin>>m;long long a,sum = n;long long x,y,def,add,mingb;if(m){cin>>x;sum -= n/x;}if(m==2){cin>>y;if(!sum)//第一次就全部把燈全關了sum += n/y;else{mingb = x*y/gcd(x,y);//最小公倍數def = n/y;add = n/mingb*2;//直接減def，實際上多減了n/mingb并且此時又開了n/mingb個燈，所以add為n/mingb*2sum += add-def;}}cout<<sum<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的1776: Press the switch（思维题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。