网站必须做电子认证吗,企业公司建设网站,做网站哪个语言强,app立即打开Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 239 Solved: 113[Submit][Status][Discuss]Description 设函数g(N)表示N的约数个数。现在给出一个数M#xff0c;求出所有M的约数x的g(x)的K次方和。 Input 第一行输入N#xff0c;K。N表示M由前N小的素数组成。接下来N行求出所有M的约数x的g(x)的K次方和。 Input 第一行输入NK。N表示M由前N小的素数组成。接下来N行第i1行有一个正整数Pi表示第Ai小的素数 有 Pi次。等式 Output 输出一个数表示答案。只需输出最后答案除以1000000007的余数。 Sample Input 2 313 Sample Output 900【样例说明】M2^1*3^354M的约数有1,2,3,6,9,18,27,54.约数个数分别为1,2,2,4,3,6,4,8.Answer1^32^32^34^33^36^34^38^3900编号 N K Pi1 50 3 100002 50 100 100003 50 20101125 100004 999 17651851 1000005 5000 836954247 1000006 4687 1073741823 1000007 4321 123456789 1000008 5216 368756432 1000009 8080 2^31-1 10000010 10086 3 2^63-111 64970 3 2^63-112 71321 3 2^63-113 350 5 2^31-114 250 6 2^31-115 110 7 2^31-116 99 8 2^31-117 80 9 2^31-118 70 10 2^31-119 60 11 2^31-120 50 12 2^31-1数据范围着实让人头大前九个是一种算法后11个是一种算法。先推一下式子f(n) (d|n)∑g(d)^k πf(pi^ai)π(g(1)^kg(pi)^k...g(pi^ai)^k)π(∑(i1 to ai1)i^k)对数据分治ai小的暴力算出x^k的前缀和大的高斯消元算出系数再套公式。至于高斯消元 先得出 a0a1*xa2*x^2...a(k1)*x^(k1)1^k2^k...x^k,同理可得 a0a1*(x1)a2*(x1)^2...a(k1)*(x1)^(k1)1^k...x^k(x1)^k 下式减上式可得a0*0a1*(x1-1)a2*((x1)^2-x^2)....a(k1)*((x1)^(k1)-x^(k1))(x1)^k不难发现a00(用手指头想想也知道不会带一个常数的因为0的多少次方都为0)所以带k1个等式消元就可以把a1-ak1求出来啦。再之后就是套公式环节注意是求(ai 1)的k次方前缀和。 #includebits/stdc.h
#define ll long long
#define maxn 100005
#define ha 1000000007
using namespace std;
ll a[maxn],n,k,mx0;
ll ans1,ci[maxn];
ll b[20][20];inline ll ksm(ll x,ll y){ll an1;for(;y;y1,xx*x%ha) if(y1) anan*x%ha;return an;
}inline void work(){mx; ll now1;for(int i1;imx;i){ci[i]ci[i-1]ksm(i,k);if(ci[i]ha) ci[i]-ha;}for(int i1;in;i){nownow*ci[a[i]1]%ha;}printf(%lld\n,now);
}inline void solve(){ll lenk1,now,pre;for(int i1;ilen;i){nowpre1;for(int j1;jlen;j){nownow*(i1)%ha;prepre*i%ha;if(jk) b[i][len1]now;b[i][j](now-preha)%ha;}}for(int i1;ilen;i){if(!b[i][i]){for(int ji1;jlen;j) if(b[j][i]){for(int l1;llen1;l) swap(b[j][l],b[i][l]);break;}}for(int ji1;jlen;j) if(b[j][i]){ll Ab[i][i],Bb[j][i],CA/B;while(B){CA/B;for(int li;llen1;l) b[i][l](b[i][l]-C*b[j][l]ha)%ha;for(int li;llen1;l) swap(b[i][l],b[j][l]);Ab[i][i],Bb[j][i];}}}for(int ilen;i;i--){ll wb[i][len1];for(int ji1;jlen;j) w(w-b[j][j]*b[i][j]%haha)%ha;b[i][i]w*ksm(b[i][i],ha-2)%ha;}for(int i1;in;i){ll tot0,nowa[i]%ha1;for(int j1;jlen;j,nownow*((a[i])%ha1)%ha) tot(totb[j][j]*now)%ha;ansans*tot%ha;}printf(%lld\n,ans);
}int main(){scanf(%lld%lld,n,k);for(int i1;in;i){scanf(%lld,ai);mxmax(mx,a[i]);}if(mx100000){work();return 0;}solve();return 0;
} 转载于:https://www.cnblogs.com/JYYHH/p/8231721.html
