POJ.2115 C Looooops

1.Problem
http://poj.org/problem?id=2115

2.Idea
ext gcd

3.Source

 Int a, b, c, k;  
 Int m;  
 // a x + b y = gcd(a, b)  
 Int extgcd(Int a, Int b, Int &x, Int &y) {  
      Int g = a; x = 1; y = 0;  
      if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;  
      return g;  
 }  
 void solve()  
 {  
      while (scanf("%lld%lld%lld%lld", &a, &b, &c, &k) > 0) {  
           if (a == 0 && b == 0 && c == 0 && k == 0) {  
                break;  
           }  
           Int m = (Int)1 << k, x, y;  
           Int g = extgcd(c, m, x, y);  
           if ((b - a) % g) {  
                printf("FOREVER\n");  
           }  
           else {  
                x = (x*((b - a) / g) % (m / g) + (m / g)) % (m / g);  
                printf("%lld\n", x);  
           }  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

LeetCode.1488 Avoid Flood in The City

1.Problem
https://leetcode.com/contest/weekly-contest-194/problems/avoid-flood-in-the-city/

2.Idea
set lower bound

3.Source

 class Solution {  
 public:  
      vector<int> avoidFlood(vector<int>& rains) {  
           int n = rains.size();  
           vector<int> emt, ans;  
           if (n == 0) return emt;  
           set<int> st;  
           map<int, int> mp;  
           ans.resize(n, -1);  
           for (int i = 0; i < n; i++) {  
                if (rains[i] == 0) {  
                     st.insert(i);  
                }  
                else {  
                     int cur = rains[i];  
                     if (mp.find(cur) == mp.end()) {  
                          mp[cur] = i;  
                     }  
                     else {  
                          if (st.size() == 0) return emt;  
                          set<int>::iterator it = st.lower_bound(mp[cur]);  
                          if (it == st.end()) return emt;  
                          else {  
                               ans[*it] = cur;  
                               st.erase(*it);  
                               mp[cur] = i;  
                          }  
                     }  
                }  
           }  
           for (int i = 0; i < n; i++) {  
                if (rains[i] > 0) ans[i] = -1;  
                else if (ans[i] == -1) ans[i] = 1;  
           }  
           return ans;  
      }  
 };  

POJ.1284 Primitive Roots

1.Problem
http://poj.org/problem?id=1284

2.Idea
Primitive roots, Euler function

3.Source

 int euler[N];  
 void solve()  
 {  
      for (int i = 0; i < N; i++) euler[i] = i;  
      for (int i = 2; i < N; i++) {  
           if (euler[i] == i) {  
                for (int j = i; j < N; j += i) {  
                     euler[j] = euler[j] / i * (i - 1);  
                }  
           }  
      }  
      int p;  
      while (scanf("%d", &p)>0) {  
           printf("%d\n", euler[p - 1]);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }