1845 Sumdiv

「1845 Sumdiv」の編集履歴（バックアップ）一覧はこちら

「1845 Sumdiv」(2006/04/17 (月) 01:49:14) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1845 Sumdiv
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1845
**解答方針
いくつかの数学的事実を用いる．

 p1^r1 p2^r2 ... pn^rn
の約数の和は
 (1 + p1 + ... + p1^r1)(1 + p2 + ... + p2^r2) ... (1 + pn + ... + pn^rn)
とかける．

フェルマーの小定理により
 a^(p-1) = 1 (mod p)
がなりたつ．

さらに，
 1 + a + a^2 + ... + a^(p-2) =
    | when a = 0 then 1
    | when a = 1 then p-1
    | otherwise  then 0
 (mod p)
がなりたつ．
**解答例
 import java.util.*;
 
 public class Main {
     final static int M = 9901;
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         
         int[] prime = new int[3000];
         makePrimeTable(prime);
         // prime[2999] = 27449
         
         int a = sc.nextInt();
         int b = sc.nextInt();
         int ans;
         if(a!=0){
             Vector<IntPair> v = new Vector<IntPair>();
             factorization(a,v,prime);
             for(IntPair p:v){
                 p.fst %= M;
                 p.snd *= b;
             }
             
             ans = 1;
             for(IntPair p:v){
                 int pa = p.fst;
                 int pb = p.snd;
                 // pb = k*(M-1) + r;
                 int k = pb/(M-1);
                 k %= M;
                 int r = pb%(M-1);
                 int product;
                 if(pa==0) product = 1;
                 else if(pa==1) product = (M-1)*k + expsum(pa,r);
                 else product = expsum(pa,r);
                 product %= M;
                 ans *= product;
                 ans %= M;
             }
         }
         else ans = 0;
         
         System.out.println(ans);
     }
     
     private static int expsum(int x,int n){
         int ret = 1;
         int add = 1;
         for(int i=1;i<=n;i++){
             add *= x;
             add %= M;
             ret += add;
             ret %= M;
         }
         return ret;
     }
 
     private static void factorization(int x,Vector<IntPair> v,int[] prime){
         for(int i=0;/*i<prime.length&&*/prime[i]*prime[i]<=x;i++){
             int cnt = 0;
             while(x%prime[i]==0){
                 x /= prime[i];
                 cnt++;
             }
             v.add(new IntPair(prime[i],cnt));
             if(x==1) break;
         }
         if(x!=1) v.add(new IntPair(x,1));
     }
     private static void makePrimeTable(int[] prime){
         int x = 2;
         int cnt = 0;
         while(cnt<prime.length){
             boolean divided = false;
             for(int i=0;i<cnt&&prime[i]*prime[i]<=x;i++){
                 if(x%prime[i]==0){
                     divided = true;
                     break;
                 }
             }
             if(!divided){
                 prime[cnt] = x;
                 cnt++;
             }
             x++;
         }
     }
 }
 
 class IntPair{
     int fst;
     int snd;
     public IntPair(int fst, int snd) {
         this.fst = fst;
         this.snd = snd;
     }
 }