UOJ Logo chtomede的博客

博客

#134. 让硬币决定吧!

2019-02-02 20:18:54 By chtomede

代码很短,如下:

#include<iostream>
#include<cmath>
using namespace std;
long long n;
int main(){
    cin>>n;
    cout<<(long long)sqrt(n)<<endl;
    return 0;
}

接下来说说蒟蒻的理解:

菜比从不一眼看出答案,上来先打表

第一次: 1 2 3 4 5 6

第二次: 2 4 6 8 10 12

第三次: 3 6 9 12 15 18

第四次: 4 8 12 16 20 24

第五次: 5 10 15 20 25 30

第六次: 6 12 18 24 30 36

然后就可以发现,这玩意关于黑体字对称,除黑体字以外的硬币都被翻过偶数次,而被反过奇数次的黑字都是平方数。

因此,硬币数的向下开平方数即为反面的硬币数。

......好像变麻烦啦......

原理:一个数可以拆成任意两数之乘积,如6=1×6又可=2×3,所以第6枚硬币可以在第1,2,3,6次时翻转,所以必为偶数次,而平方数能拆成㎡的形式,在第m次时反转一次,故为奇数次

评论

NaCl
刚在单墫《初等数论的知识与问题》上看到这个结论……

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。