(a^b)%c

long long power(long long x,int y)
{
    if (!y)
    return 1;
    long long ret=power(x,y/2);
    ret=(ret*ret)%mod;
    if (y%2)
    ret=(ret*x)%mod;
    return ret;
}

P.Q^(-1) mod 1e9+7

Fermat’s little theorem

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number a ^p – a is an integer multiple of p.

Here p is a prime number
a^p ≡ a (mod p).

Special Case: If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that a ^p-1-1 is an integer multiple of p.

a^p-1 ≡ 1 (mod p)
OR
a^p-1 % p = 1
Here a is not divisible by p.

Take an Example How Fermat’s little theorem works
Examples:

 P = an integer Prime number   
 a = an integer which is not multiple of P  
 Let a = 2 and P = 17 
 
 According to Fermat's little theorem 
  2 17 - 1     ≡ 1 mod(17)
 we got  65536 % 17 ≡ 1   
 that mean (65536-1) is an multiple of 17 

Use of Fermat’s little theorem
If we know m is prime, then we can also use Fermats’s little theorem to find the inverse.
a^m-1 ≡ 1 (mod m)
If we multiply both sides with a-1, we get
a^-1 ≡ a ^m-2 (mod m)
Below is the Implementation of above

filter_none edit
play_arrow
brightness_4

// C++ program to find modular inverse of a // under modulo m using Fermat's little theorem. // This program works only if m is prime. #include <bits/stdc++.h> using namespace std;    // To compute x raised to power y under modulo m int power(int x, unsigned int y, unsigned int m);    // Function to find modular inverse of a under modulo m // Assumption: m is prime void modInverse(int a, int m) {     if (__gcd(a, m) != 1)         cout << "Inverse doesn't exist";        else {            // If a and m are relatively prime, then         // modulo inverse is a^(m-2) mode m         cout << "Modular multiplicative inverse is "              << power(a, m - 2, m);     } }    // To compute x^y under modulo m int power(int x, unsigned int y, unsigned int m) {     if (y == 0)         return 1;     int p = power(x, y / 2, m) % m;     p = (p * p) % m;        return (y % 2 == 0) ? p : (x * p) % m; }    // Driver Program int main() {     int a = 3, m = 11;     modInverse(a, m);     return 0; }

Output :

Modular multiplicative inverse is 4

Bài A - Codeforces Beta Round #72 (Div.1 Only)

Valera rất quan tâm đến phép thuật. Phép thuật thu hút anh ta đến mức anh ta nhìn thấy nó ở khắp mọi nơi. Ông giải thích bất kỳ hiện tượng kỳ lạ và kỳ lạ nào thông qua sự can thiệp của các thế lực siêu nhiên.
   Valera hoàn toán vô tình có được một mảnh giấy da cổ, trên đó có một dãy số được viết. Anh ta nghĩ rằng những con số trong mảng này không phải là ngẫu nhiên. Kết quả của nghiên cứu sâu rộng Valera đã tìm ra một tính chất tuyệt vời mà một mảng ma thuật nên có: có một mảng được định nghĩa là ma thuật nếu tối  thiểu và tối đa trùng khớp.
 Anh ấy quyết định chia sẻ khám phá nổi bật với bạn, nhưng anh ấy nhờ bạn giúp đỡ để đáp lại. Mặc dù có trí thông minh và trí thông minh to lớn, Valera tính rất tệ và vì vậy bạn sẽ phải hoàn thành công việc của mình. Tất cả những gì bạn phải làm là đếm số lượng các phép thuật con của mảng số gốc, được viết trên giấy da. Subarray được định nghĩa là chuỗi không trống của các phần tử liên tiếp.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n (1<=n<=10^5). Dòng thứ hai chứa một mảng các số nguyên a(1),a(2),...,a(n).
Đầu ra:
+ In ra một dòng duy nhất là câu trả lời của bài toán: số lượng mảng con, thỏa mãn mảng đó là ma thuật.
Ví dụ:
Đầu vào:
4
2 1 1 4
Đầu ra:
5
Đầu vào:
5
-2 -2 -2 0 1
Đầu ra:
8
Giải thích:
Ở ví dụ đầu tiên: [1;1],[2;2],[3;3],[4;4],[2;3]
Ở ví dụ thứ hai: [1;1],[2;2],[3;3],[4;4],[5;5],[1,2],[2,3],[1,3].
Hướng dẫn:
Lời giải:

#include<iostream>
long long n,S,r,p=2e9,x;
main(){
  for(std::cin>>n;std::cin>>x;S+=++r)if(x!=p)r=0,p=x;
  std::cout<<S;
}

Bài C - Codeforces Beta Round #1

Bài C:
Đề bài:
  Ngày nay tất cả các rạp xiếc ở Berland đều có một đấu trường với đường kính 13 mét, nhưng trong mọi thứ thì khác.
  Trong các đấu trường Berland cổ đại trong các rạp xiếc được định hình là một đa giác (tam giác) đều, kích thước và số lượng góc có thể thay đổi tử rạp xiếc này đến rạp xiếc khác. Ở mỗi góc của đấu trường có một cây cột đặc biệt, và sợi dây được căng giữa các cây cột đánh dấu các cạnh của đấu trường.
  Gần đây, các nhà khoa học từ Berland đã phát hiện ra phần còn lại của đấu trường xiếc cổ đại. Họ chỉ tìm thấy ba cây cột, những cái khác đã bị thời gian pháy hủy.
  Bạn được cho các tọa độ của ba cây trụ. Tìm ra giá trị nhỏ nhất của đấu trường có thể.
Đầu vào:
+ Đầu vào gồm 3 dòng, mỗi dòng là một cặp số - tọa độ của các cột. Bất kì tọa độ nào cũng không quá 1000 by absolute value, và được cho nhiều nhất 6 chữ số sau hàng thập phân.
Đầu ra:
+ In ra diện tích nhỏ nhất có thể của đầu trường cổ. Con số này chính xác tới ít nhất 6 số phần thập phân.
Ví dụ:
Đầu vào:
0.000000 0.000000
1.000000 1.000000
0.000000 1.000000
Đầu ra:
1.00000000
Hướng dẫn:
 Các điểm có thể là các đỉnh của N- đa giác đều khi và chỉ khi với mỗi cặp, sự khác biệt của các góc cực của chúng (khi nhìn từ tâm đa giác) của 2*pi/N. Tất cả các điểm nằm trên đường tròn với cùng tâm với đa giác. Chúng ta có thể xác định vị trí trung tâm của đa giác / vòng tròn [nhưng chúng ta có thể tránh điều này, vì một hợp âm như giả sử, (x(1),y(1))-(x(2),y(2))] được nhìn thấy ở góc lớn hơn gấp đôi so với tâm điểm khác của một điểm khác của đường tròn (x(3),y(3))]
 Có nhiều cách để xác định vị trí trung tâm của vòng tròn, cách tôi đã xây dựng là xây dựng trung điểm vuông góc với các phân đoạn (x1,y1)-(x2,y2) và (x2,y2)-(x3,y3) ở dạng y=a*x+b và tìm giao điểm của chúng. Công thức y=a*x+b có nhược điểm là không thể sử dụng nếu đường thẳng song song với y, cách giải quyết có thể là xoay tất cả các điểm theo góc ngẫu nhiên (sử dụng công thức xl=x*cos(a)-y*sin(a),y'=y*cos(a)+x*sin(a)) cho đến khi không có đoạn nào nằm ngang (và do đó không có đường vuông góc nào là dọc).
  Sau khi biết tọa độ của tâm, chúng ta sử dụng hàm ưa thích: , trả về góc trong phần tư phải: a[i]=atan2(y[i]-ycenter,x[i]-xcenter) atan2.
  Diện tích của đa giác đều tăng khi tăng N, do đó có thể chỉ cần lặp qua tất cả các giá trị có thể có trên N theo thứ tự tăng dần và thoát khỏi chu kỳ khi tìm thấy N thỏa mãn đầu tiên.
 Sử dụng sin(x) là làm cho nó dễ dàng: sin(x)=0 khi x là bội của pi. Vì vậy, đối với các điểm thuộc về đa giác N, đa giác N đều.
sin(N*(a[i]-a[j])/2)=0.
 Bởi vì số học chính xác hữu hạn, fabs(sin(N*(a[i]-a[j])/2)).
Lời giải:

#include<cstdio>
#include<cmath>
#define D double
#define S(x) ((x)*(x))
#define G(t) a[t]=x[t]-x[2];b[t]=y[t]-y[2];c[t]=(S(x[t])+S(y[t])-S(x[2])-S(y[2]))/2;
#define M(p,q) (p[0]*q[1]-p[1]*q[0])
D g(D a,D b){return fabs(b)<1e-4?a:g(b,fmod(a,b));}
D x[3],y[3],a[3],b[2],c[2],A,X,Y;
int main()
{
for(int i=0;i<3;++i)scanf("%lf%lf",x+i,y+i);
G(0);G(1);
X=M(c,b)/M(a,b);
Y=M(a,c)/M(a,b);
for(int i=0;i<3;++i)a[i]=atan2(x[i]-=X,y[i]-=Y);
A=g(M_PI*2,g(fabs(a[1]-a[0]),fabs(a[2]-a[0])));
printf("%lf\n",(S(x[0])+S(y[0]))*sin(A)*M_PI/A);
}