程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1452 Happy 2004

hdu1452 Happy 2004

編輯:C++入門知識

原題:http://acm.hdu.edu.cn/showproblem.php?pid=1452


等比數列求和公式:\(之前忘記了。+ =)


奇性函數:

在數論中,積性函數<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPsrH1rjSu7j2tqjS5dPyzqrV/dX7yv08ZW0+bjwvZW0+ILXEy+PK9bqvyv08ZW0+ZihuKTwvZW0+o6zT0Mjnz8LQ1NbKo7o8ZW0+ZigxKQogPSAxPC9lbT6jrMfStbE8ZW0+YTwvZW0+ILrNPGVtPmI8L2VtPiC7pdbKyrGjrDxlbT5mKGFiKSA9IGYoYSkgZihiKTwvZW0+oaM8L3A+CjxwPgrI9NK7uPa6r8r9PGVtPmYobik8L2VtPiDT0Mjnz8LQ1NbKo7o8ZW0+ZigxKSA9IDE8L2VtPqOsx9K21MG9uPbL5tLi1f3V+8r9PGVtPmE8L2VtPiC6zTxlbT5iPC9lbT4gtvjR1KOssrvWu8/e1eLBvcr9u6XWysqxo6w8ZW0+ZihhYikgPSBmKGEpZihiKTwvZW0+ILa8s8nBoqOs1PKzxrTLuq/K/c6qzerIq7v90NS6r8r9oaM8L3A+CjxwPgrU2sr9wtvS1M3itcTG5Mv7yv3Rp8Hs0/LW0Mv5zLi1vbXEPHN0cm9uZz67/dDUuq/K/Twvc3Ryb25nPs2os6PKx9a4PHN0cm9uZz7N6siru/3Q1Lqvyv08L3N0cm9uZz6hozwvcD4KPHA+CjwvcD4KPGgyPgrA/dfTPC9oMj4KPHVsPgo8bGk+ptUoPGVtPm48L2VtPikgo63Ft8CtptW6r8r9o6y8xsvj0+s8ZW0+bjwvZW0+u6XWyrXE1f3V+8r91q7K/cS/PGxpPqbMKDxlbT5uPC9lbT4pIKOtxKyxyM7ay7m6r8r9o6y52NPat8fGvbe9yv21xNbK0vLX08r9xL88bGk+Z2NkKDxlbT5uPC9lbT4sPGVtPms8L2VtPikgo63X7rTzuavS8tfTo6y1sTxlbT5rPC9lbT65zLaotcTH6b/2PGxpPjxpbWcgY2xhc3M9"tex" alt="\sigma_k" src="http://www.2cto.com/uploadfile/Collfiles/20140409/20140409090159258.png">(n): 除數函數,n的所有正因子的k次冪之和,當中k可為任何復數。在特例中有:

  • \sigma_0(n) = d(n) - n的正因子數目
  • \sigma_1(n) = \sigma(n) - n的所有正因子之和
  • 1(n) -不變的函數,定義為 1(n)=1 (完全積性)
  • Id(n) -單位函數,定義為 Id(n)=n (完全積性)
  • Idk(n) -冪函數,對於任何復數、實數k,定義為Idk(n) = nk (完全積性)
    • Id0(n) = 1(n) 及
    • Id1(n) = Id(n)
    • ε(n) -定義為:若n = 1,ε(n)=1;若n > 1,ε(n)=0。有時稱為“對於狄利克雷卷積的乘法單位”(完全積性)
    • (n/p) -勒讓德符號,p是固定質數(完全積性)
    • λ(n) -劉維爾函數,關於能整除n的質因子的數目
    • γ(n),定義為γ(n)=(-1)ω(n),在此加性函數ω(n)是不同能整除n的質數的數目
    • 所有狄利克雷特征均是完全積性的

    • //上面的資料摘自維基百科。

      可見本題目為:除數函數,不完全奇性函數。


      const int INF=0x3f3f3f3f; 另外參見了大神的代碼,發現最大值可以這麼表示。


      原因如下:http://blog.csdn.net/dr5459/article/details/8211408

      有如下性質:

      1、當gcd(a,b)=1時,s[a*b]=s[a]*s[b].

      2、當p為素數時,s[p^n]=p^0+p^1+……+p^n=(p^(n+1)-1)/(p-1)

      3、(a * b ) / c % M = a % M * b % M * inv(c);

      其中inv(c)即滿足 (c*inv(c))%M=1的最小整數,這裡M=29

      inv(1)= 1, inv(2)=15,inv(166)=18;

      S((2^2)^x) * S(3^x) * S(167 ^ n) = S(2004^n);

      //============================================================================
      // Name        : Math_hdu1452.cpp
      // Author      : vit
      // Version     :
      // Copyright   : Your copyright notice
      // Description : Hello World in C++, Ansi-style
      //============================================================================
      
      #include 
      #include 
      #include 
      
      #define MOD 29
      
      using namespace std;
      
      int pow(int a,int b)
      {
          int ans=1;
          while(b)
          {
              if(b&1)//judge odd or even
              	ans = (ans * a) % MOD;
              a = a * a % MOD;
              b=b>>1;
          }
          return ans;
      }
      
      
      int main() {
      	int x;
      	int a, b, c;
      	while(cin >> x && x){
      		a = (pow(2,2*x + 1) - 1) * 1 % MOD;
      		b = (pow(3,x + 1) - 1) * 15 % MOD;
      		c = (pow(167, x + 1) - 1) * 18 % MOD;
      
      		cout << a * b * c % MOD << endl;
      	}
      	return 0;
      }
      



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved