Super Sum

题目链接： https://vjudge.net/contest/174844#problem/J；

题意：给一群a,b,c,求解a1^m1*a2^m2*a3^m3*a4^m4......an^mn所有可能的和，其中b<=mi<=c;

思路：看到这题的时候，我联想到了求n因子的公式，设n=p1^e1*p2^e2*P3^e3*p4^e4......,则n的所有因子的和为：（1+p1+p1^2+p1^3+.....p1^e1）*(1+p2+p2^2+...p2^e2)*......*(1+pr+pr^2+......+pr^er);现在n的幂是有范围的，所以我猜想sum=(a1^b1+.....a1^c1)*(a2^b2+....a2^c2)*(a3^b3+.....a3^c3)*.....(an^bn+......an^cn);因为是在比赛，所以在测试几组数据正确的后我并没有证明而是直接用了，比赛后求证了一下公式的正确性，假设a2-an之间的和s1已知，那么求sum只需要s1乘以a^x(b1<=x<=c1)的值即可，即sum=(a1^b1+...+a1^c1)*s1;然后再假设a3-an之间的和s2已知，那么sum=(a1^b1+....a1^c1)*(a2^b2+......a2^c2)*s2;依此类推，即可求得公式；实现的话，每输入一组a,b,c就可以处理数据，a^b+....a^c可直接用等比数列求和公式，[a^b(a^(c-b+1)-1)]/(a-1),这里注意a是否等于1的情况，因为b非常大，如果直接把和求出来肯定会存不下，取余的话因为要除以(a-1)就会致使答案错误，利用A/B公式就可以了，x=A/B(mod n)可转化为A*B^(phi(n)-1)mod n，因为 1000000007为素数，所以phi为 1000000006；

具体代码如下：

#include<stdio.h>
long long l=1000000007;
long long pow(long long a,long long n)
{
    int t=1;
    while(n>0)
    {
        if(n&1)
            t=t*a%l;
        a=a*a%l;
        n>>=1;
    }
    return t;
}
long long JS(long long n,long long y,long long x)
{
    long long s,b,c,a;
    if(n==1)
       s=(x-y+1)%l;
    else
    {
        a=pow(n,y)%l;
        b=(a*(pow(n,x-y+1)-1)%l)%l;
        c=pow(n-1,l-2)%l;
        s=b*c%l;
    }
    return s;
}
int main()
{
    long long t,s,a,b,c,m;
    scanf("%lld",&t);
    for(int i=1;i<=t;i++)
    {
        scanf("%lld",&m);
        s=1;
        for(int j=1;j<=m;j++)
        {
            scanf("%lld %lld %lld",&a,&b,&c);
            s=s*JS(a,b,c)%l;
        }
        printf("Case #%d: %lld\n",i,s);
    }
    return 0;
}