UVA 10110 Light, more light【经典开灯问题】

Light, more light

Time Limit: 3000ms Memory Limit: 131072KB This problem will be judged on  UVA. Original ID:  10110 64-bit integer IO format:  %lld      Java class name:  Main Prev  Submit  Status  Statistics  Discuss   Next

Type:  None   None Graph Theory      2-SAT     Articulation/Bridge/Biconnected Component      Cycles/Topological Sorting/Strongly Connected Component      Shortest Path          Bellman Ford         Dijkstra/Floyd Warshall      Euler Trail/Circuit      Heavy-Light Decomposition     Minimum Spanning Tree      Stable Marriage Problem      Trees     Directed Minimum Spanning Tree      Flow/Matching          Graph Matching             Bipartite Matching              Hopcroft–Karp Bipartite Matching              Weighted Bipartite Matching/Hungarian Algorithm          Flow              Max Flow/Min Cut             Min Cost Max Flow  DFS-like      Backtracking with Pruning/Branch and Bound      Basic Recursion     IDA* Search      Parsing/Grammar     Breadth First Search/Depth First Search      Advanced Search Techniques          Binary Search/Bisection         Ternary Search  Geometry      Basic Geometry     Computational Geometry      Convex Hull      Pick's Theorem Game Theory      Green Hackenbush/Colon Principle/Fusion Principle      Nim     Sprague-Grundy Number  Matrix     Gaussian Elimination      Matrix Exponentiation Data Structures      Basic Data Structures     Binary Indexed Tree      Binary Search Tree      Hashing     Orthogonal Range Search      Range Minimum Query/Lowest Common Ancestor      Segment Tree/Interval Tree     Trie Tree      Sorting      Disjoint Set String      Aho Corasick     Knuth-Morris-Pratt      Suffix Array/Suffix Tree Math      Basic Math     Big Integer Arithmetic      Number Theory         Chinese Remainder Theorem          Extended Euclid          Inclusion/Exclusion         Modular Arithmetic      Combinatorics          Group Theory/Burnside's lemma         Counting      Probability/Expected Value  Others     Tricky      Hardest     Unusual      Brute Force     Implementation      Constructive Algorithms     Two Pointer      Bitmask     Beginner      Discrete Logarithm/Shank's Baby-step Giant-step Algorithm      Greedy     Divide and Conquer  Dynamic Programming                   Tag it!

[PDF Link]

  Light, more light

The Problem

There is man named "mabu" for switching on-off light in our University. He switches on-off the lights in a corridor. Every bulb has its own toggle switch. That is, if it is pressed then the bulb turns on. Another press will turn it off. To save power consumption (or may be he is mad or something else) he does a peculiar thing. If in a corridor there is `n' bulbs, he walks along the corridor back and forth `n' times and in i'th walk he toggles only the switches whose serial is divisable by i. He does not press any switch when coming back to his initial position. A i'th walk is defined as going down the corridor (while doing the peculiar thing) and coming back again.

Now you have to determine what is the final condition of the last bulb. Is it on or off?   

The Input

The input will be an integer indicating the n'th bulb in a corridor. Which is less then or equals 2^32-1. A zero indicates the end of input. You should not process this input.

The Output

Output " yes" if the light is on otherwise " no" , in a single line.

Sample Input

3 6241 8191 0

Sample Output

no yes no

AC代码：

#include <iostream> #include <cmath> using namespace std; int main() { int n; while(cin>>n,n) { int x=sqrt(n*1.0); if(x*x==n) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }