Phi 1 số và UCLN

    1. ll gcd(ll a, ll b){
    2. if(a==0||b==0) return a+b;
    3. if(a==b) return a;
    4. return gcd(b,a%b);
    5. }
    6. ll phi(ll n){
    7. ll ans = n;
    8. ll d = 2,dem;
    9. while(d*d<=n){
    10. dem = 0;
    11. while(n%d==0){
    12. n/=d;
    13. dem++;
    14. }
    15. if(dem>0) ans-=ans/d;
    16. d++;
    17. }
    18. if(n>1) ans-=ans/n;
    19. return ans;
    20. }

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Sinh Test trong Python va code AC

P1: #file = "C:/New folder/aka/1.inp" #with open(file) as f: # a,b=[int(x) for x in next(f).split()] #print(a) #print(b) def gg(id): file= "C:/New folder/aka/" +id+ ".inp" with open (file) as f: a,b=[ int (x) for x in next (f).split()] products = set () for pair in [(x,y) for x in range ( 2 ,a+ 1 ) for y in range ( 2 ,b+ 1 )]: products.add(pair[ 0 ]**pair[ 1 ]) return len (products) x= range ( 1 , 101 ) for i in x: id= str (i) file1 = "C:/New folder/aka/" +id+ ".out" f= open (file1, "w" ) f.write( str (gg(id))) f.close() P2: a,b=[ int (x) for x in input ().split()] product = set () for pair in [(x,y) for x in range ( 2 ,a+ 1 ) for y in range ( 2 ,b+ 1 )]: product.add(pair[ 0 ]**pair[ 1 ]) print ( len (product))
Đọc thêm

Học về Segment Tree

Hình ảnh
Segment Tree được sử dụng trong trường hợp có nhiều truy vấn phạm vấn phạm vi trên mảng và sửa đổi các phần tử của cùng một mảng. Ví dụ, tìm tổng của tất cả các phần tử trong một mảng từ chỉ số L đến R, hoặc tìm giá trị nhỏ nhất của tất cả các phần tử trong 1 mảng từ chỉ số L đến R. Những vấn đề này có thể được giải quyết dễ dàng với một trong những cấu trúc dữ liệu linh hoạt nhất. Segment Tree. Segment Tree là gì ? Segment Tree cơ bản là một cây nhị phân nhằm lưu trữ một đoạn. Mỗi nút trong Segment Tree đại diện cho một đoạn. Xét mảng A có kích thước N, và 1 cây Segment Tree T tương ứng. 1. Gốc của cây T sẽ đại diện cho cả mảng: A[0:N-1]. 2. Mỗi lá của cây T sẽ đại diện một phần tử A[i] thỏa mãn 0<=i<N. 3. Mỗi nút nút của cây T đại diện cho một đoạn A[i:j] với 0<=i<j<N. Gốc của Segment Tree đại diện cho cả mảng A[0:N-1]. Sau đó nó chia đôi thành một nữa và 2 đứa trẻ của gốc sẽ đại diện cho A[0:(N-1)/2]  và A[(N-1)/2+1;(N-1)]. Vì vậy, ở mỗi bước, Segment lại chi
Đọc thêm

Cách tính a*b mod m , a^b mod m , a^(-1) mod m với m không phải là số nguyên tố (inversion có nghĩa khi (a,m)=1)

#include <bits/stdc++.h> using namespace std ; #define ll long long #define MOD (ll)(1000000000000000009) ll inv ( ll a , ll mod ){ ll r = mod ; ll nr = a ; ll t = 0 ; ll nt = 1 ; ll tmp ; while ( nr != 0 ){ ll q = r / nr ; tmp = nt ; nt = t - q * nt ; t = tmp ; tmp = nr ; nr = r - q * nr ; r = tmp ; } if ( r > 1 ) return - 1 ; // no inverse if ( t < 0 ) t += mod ; return t ; } ll f ( ll a , ll n , ll mod ){ ll res = a , ans = 0 ; while ( n ){ if ( n % 2 ) ans = ( ans + res ) % mod ; res = ( res + res ) % mod ; n /= 2 ; } return ans ; } ll po ( ll a , ll n , ll mod ){ ll res = a , ans = 1 ; while ( n ){ if ( n % 2 ) ans = f ( ans , res , mod ); res = f ( res , res , mod ); n /= 2 ; } return ans ; } int main (){ ll x , y , z , m , dem = 0 , res1 , res2 , res , tmp
Đọc thêm