• 【无标题】

    一.整数分解的唯一性与gcd,lcm

    1.

    P1072[NOIP2009 提高组] Hankson 的趣味题
    题意：已知a,a1,b,b1 x与a的的最大公约数是a1,x与b的最大公倍数是b1
     求解有多少满足的x
    思路:
    gcd(x,a)=a1，x=k1a1,a=k2a1,gcd(k1,k2)=1
    反证：gcd(k1,k2)=k(k!=1),k1=kp,k2=kq ->x=kk1a1,a=kk2a1,gcd(x,y)=ka1
    结论进一步可推得：对于两个正整数a,b,若gcd(a,b)=k,gcd(a/k,b/k)=1
    lcm(x,b)=b1 => x*b/gcd(x,b)=b1 =>gcd(x,b)=x*b/b1 => gcd(b1/b,b1/x)=1
    结论进一步可推得：对于两个正整数a,b,若lcm(a,b)=k,gcd(k/a,k/b)=1
     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #define endl '\n'
    13. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    14. #define ms(x,y) memset(x,y,sizeof x);
    15. #define YES cout<<"YES"<<'\n';
    16. #define NO  cout<<"NO"<<'\n';
    17. #define fr(i,z,n) for(int i = z;i <= n; i++)
    18. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    19. typedef long long ll;
    20. const ll maxn = 2e5 + 10, inf = 1e18;
    21. const ll mod = 1e9 + 7;
    22. using namespace std;
    23. int gcd(int a, int b) {                    //辗转相除法求最大公约数
    24.     return !b ? a : gcd(b, a % b);
    25. }
    26. void solve() {
    27.     int a, a1, b, b1;
    28.     cin >> a >> a1 >> b >> b1;
    29.     int ans = 0;
    30.     int x = b1;
    31.     set<int>s;
    32.     for (int i = 1; i * i <= x; i++) {                //找出最大公倍数的因子
    33.         if (x % i == 0) {
    34.             s.insert(i);
    35.             s.insert(x / i);
    36.         }
    37.     }
    38.     for (auto y : s) {                        //枚举因子
    39.         if (y % a1 == 0 && gcd(y / a1, a / a1) == 1 && gcd(b1 / y, b1 / b) == 1) {
    40.             ans++;
    41.         }
    42.      }
    43.      cout << ans << '\n';
    44.  }
    45. signed main()
    46. {
    47.     ios;
    48.     int t=1;
    49.     cin >> t;
    50.     while (t--) {
    51.         solve();
    52.     }
    53. }

    2.

    cf1866/problem/B
    给定两个数x,y的的质因数分解式Ai，Bi表示x的质数，指数;Ci,Di表示y的质数，指数
     求有多少对p,q满足lcm(p,q)=x,gcd(p,q)=y
    思路1.p*q=x*y  2.对于某个质数的指数，gcd相当于取min，lcm相当于取max
    对于某个素数，
    1.若Bi 2.Bi=Di,ans不变
    3.Bi>Di,ans=ans*2
     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    13. #define ms(x,y) memset(x,y,sizeof x);
    14. #define YES cout<<"YES"<<'\n';
    15. #define NO  cout<<"NO"<<'\n';
    16. #define fr(i,z,n) for(int i = z;i <= n; i++)
    17. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    18. typedef long long ll;
    19. const int N = 2000005, mod = 998244353;
    20. using namespace std;
    21. int a[N];
    22. int b[N];
    23. int c[N];
    24. int d[N];
    25. int mp1[N];
    26. int mp[N];
    27. void solve() {
    28.     int n;
    29.     cin >> n;
    30.     fr(i, 1, n) {
    31.         cin >> a[i];
    32.     }
    33.     fr(i, 1, n) {
    34.         cin >> b[i];
    35.         mp1[a[i]] = b[i];
    36.     }
    37.     int m;
    38.     cin >> m;
    39.     fr(i, 1, m) {
    40.         cin >> c[i];
    41.     }
    42.     fr(i, 1, m) {
    43.         cin >> d[i];
    44.         mp[c[i]] = d[i];
    45.     }
    46.     int ans = 1;
    47.     for (int i = 1; i <= 2000000; ++i){
    48.         if (mp1[i] < mp[i]) {
    49.             cout << 0 << '\n';
    50.             return;
    51.         }
    52.         else if (mp1[i] > mp[i]) {
    53.             ans *= 2;
    54.             ans %= mod;
    55.         }
    56.     }
    57.     cout << ans%mod << '\n';
    58. }
    59. signed main()
    60. {
    61.     ios;
    62.     int t = 1;
    63.     //cin >> t;
    64.     while (t--) {
    65.         solve();
    66.     }
    67. }

    3.

    P1593 因子和
    求a^b得因子和，对出它对 9901 取模的结果
    a<=5e7,b<=5e7
    思路：推导过程：整数的唯一分解定理，对a进行质因数分解
     a=p1^k1 *p2^k2 *p3^k3 ...*pn^kn->对a^b进行质因数分解
    a^b=p1^(k1*b) *p2^(k2*b)...*pn^(kn*b)
    因子和求解 ans=(1+p1^1+p1^2...p1^(k1*b))*(1+p2^1+p2^2...p2^(k2*b)*...*(1+pn^1+pn^2...pn^(n*b)
    等比数列求和qi^n-1/qi-1相乘
    除法逆元
    当qi-1与mod互质时，逆元为pow(qi-1,mod-2)
    不互质时，(p-1)%mod==0,p%mod==1,->(1+pi^1+pi^2...pi^(k1*b))%mod->1+k1*b

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    13. #define ms(x,y) memset(x,y,sizeof x);
    14. #define YES cout<<"YES"<<'\n';
    15. #define NO  cout<<"NO"<<'\n';
    16. #define fr(i,z,n) for(int i = z;i <= n; i++)
    17. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    18. #define int long long
    19. typedef long long ll;
    20. const ll maxn=2e5+10,inf = 1e18 ; 
    21. const ll mod = 9901;
    22. using namespace std;
    23. int mp[10010][2];
    24.  
    25. ll poww(ll x, ll k) {
    26.     if (k == 1) return x;
    27.     if (k == 0) return 1;
    28.     ll tmp = poww(x, k / 2);
    29.     if (k & 1) return tmp * tmp % mod * x % mod;
    30.     return tmp * tmp % mod;
    31. }
    32.  
    33. void solve() {
    34.     int a, b;
    35.     cin >> a >> b; 
    36.     if (a== 0) {                         //特判
    37.         cout << 0 << '\n';
    38.         return;
    39.     }
    40.     int cnt = 0;
    41.     for (int i = 2; i * i <= a; i++) {
    42.         if (a % i == 0) {
    43.             mp[++cnt][0]=i;
    44.             mp[cnt][1] = 1;
    45.             a /= i;
    46.             while (a % i == 0) {
    47.                 mp[cnt][1]++;
    48.                 a /= i;
    49.             }
    50.         }
    51.     }
    52.     if (a != 1) {
    53.         mp[++cnt][0] = a;
    54.         mp[cnt][1]++;
    55.     }
    56.     int ans = 1;
    57.     fr(i, 1, cnt) {
    58.         int x = mp[i][0];
    59.         int y = mp[i][1];
    60.         if (x%mod==1) {                
    61.             ans = ans%mod * ( y * b + 1) % mod;
    62.         }
    63.         else {         //互质
    64.             ans = ans%mod * (((poww(x, (y * b + 1) % mod)) - 1 + mod) % mod) * (poww((x - 1+mod)%mod, mod - 2) % mod);
    65.         }
    66.     }
    67.     cout << (ans%mod+mod)%mod<< '\n';
    68. }
    69. signed main(){
    70.     ios;
    71.     int t=1;
    72.     //cin >> t;
    73.     while (t--) {
    74.         solve();
    75.     }
    76. }

    4.

    P1414 又是毕业季II
    题意：老师给每位同学评了一个能力值。从n个学生中挑出k个人使得他们的默契程度（即能力值的最大公约数）最大
    总共 n 行，第i 行为k=i情况下的最大默契程度。
    n<=10^4,m<=10^6
    k个数中最大公约数：k个数中共有的因子最大的
    于是可以将所有数的因子找出并记录个数
    因为因子值越小,个数越多,满足单调性,记录最大值，不断缩小直到个数大于等于k
     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #define endl '\n'
    12. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    13. #define ms(x,y) memset(x,y,sizeof x);
    14. #define YES cout<<"YES"<<'\n';
    15. #define NO  cout<<"NO"<<'\n';
    16. #define fr(i,z,n) for(int i = z;i <= n; i++)
    17. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    18. typedef long long ll;
    19. const ll maxn = 2e5 + 10, inf = 1e18;
    20. const ll mod = 1e9 + 7;
    21. using namespace std;
    22. int a[maxn];
    23. void solve() {
    24.     int n;
    25.     cin >> n;
    26.     map<int, int>mp;
    27.     int Max = 0;
    28.     fr(i, 1, n) {
    29.         cin >> a[i];
    30.         Max = max(Max, a[i]);
    31.         for (int j = 1; j *j <= a[i]; j++) {
    32.             if (a[i] % j == 0) {
    33.                 mp[j]++;
    34.                 if (j* j != a[i]) {
    35.                     mp[a[i]/j]++;
    36.                 }
    37.             }
    38.         }
    39.     }
    40.     fr(i, 1, n) {
    41.         while (mp[Max] < i)  Max--;
    42.         cout << Max << '\n';
    43.     }
    44. }
    45. signed main()
    46. {
    47.     ios;
    48.     int t = 1;
    49.     //cin >> t;
    50.     while (t--) {
    51.         solve();
    52.     }
    53. }

    二。组合数恒等式  ->杨辉三角

    P2822[NOIP2016 提高组] 组合数问题
    题意：给定n,m,k,对于所有的0<=i<=n,0<=j<=min(i,m),有多少对C(j,i)%k==0
    思路：
    1.组合数公式  50分
    2.组合恒等式  C(n,m)=C(n-1,m-1)+C(n-1,m)->杨辉三角(n相当于行，m相当于列，每个数等于上方两数之和)
    杨辉三角的第n行的m个数可表示为 C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。
    预处理出杨辉三角，然后对每个数%k,二维前缀和，特殊的对于每行比上一行多出的进行处理
     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #define endl '\n'
    13. #define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    14. #define ms(x,y) memset(x,y,sizeof x);
    15. #define YES cout<<"YES"<<'\n';
    16. #define NO  cout<<"NO"<<'\n';
    17. #define fr(i,z,n) for(int i = z;i <= n; i++)
    18. #define ufr(i,n,z) for(int i = n;i >= z; i--)
    19. typedef long long ll;
    20. const ll maxn=2e5+10,inf = 1e18 ; 
    21. const ll mod = 1e9 + 7;
    22. using namespace std;
    23. int a[maxn];
    24. int c[2005][2005];
    25. int s[2005][2005];                     //记录矩阵前缀和
    26. int t, k;
    27. void init() {
    28.     c[1][1] = 1;
    29.     fr(i, 0, 2000) {
    30.         c[i][0] = 1;
    31.     }
    32.     fr(i, 2, 2000) {
    33.         fr(j, 1, i) {
    34.             c[i][j] = (c[i - 1][j - 1] + c[i - 1][j])%k;
    35.         }
    36.     }
    37.     //fr(i, 1, 10) {
    38.     //    fr(j, 0, i) {
    39.     //        cout << c[i][j] << ' ';
    40.     //    }
    41.     //    cout << '\n';
    42.     //}
    43.     fr(i, 1, 2000) {
    44.         fr(j, 1, i) {
    45.             s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; //二维前缀和
    46.             if (c[i][j] == 0) s[i][j] += 1;
    47.         }
    48.         s[i][i] = s[i][i - 1];
    49.     }
    50.     /*fr(i, 1, 10) {
    51.         fr(j, 1, i) {
    52.             cout << s[i][j] << ' ';
    53.         }
    54.         cout << '\n';
    55.     }*/
    56.     
    57. }
    58.  void solve(){
    59.      cin >> t >> k;
    60.      init();
    61.      fr(i, 1, t) {
    62.          int n, m;
    63.          cin >> n >> m;
    64.          if (m > n)  m = n;
    65.          cout << s[n][m] << '\n';
    66.      }
    67.  }
    68. signed main()
    69. {
    70.     ios;
    71.     int t=1;
    72.     //cin >> t;
    73.     while (t--) {
    74.         solve();
    75.     }
    76. }

  • 相关阅读:
    （LeetCode C++）有效的括号
    css 固定图片尺寸16:9
    (二)、基于 LangChain 实现大模型应用程序开发 | 对话记忆模块 Memory
    运放电压跟随器为什么要加电阻
    Redis 的缓存过期策略
    我的PMP学习考试心得
    Python基于django的图书商城管理系统毕业设计源码110938
    Anntec ZKUXFT XT2 FGPA卡DPDK使用方法
    Hive调优方法
    C语言基础知识
  • 原文地址：https://blog.csdn.net/m0_75027890/article/details/133691502