大意：给出一串数 他们的积为Ｂ 其和为Ａ 求Ｂ mod A
Description 由于某些原因菲莉丝拿到了贤者之石，所以好像变得很厉害了 好像变得很厉害的菲莉丝想要炼成幻想乡，其中有一个原料是稗田一族对幻想乡历史的记录。现在菲莉丝拿到了一个被某只魔粘性精神体加密过的的卷轴。 密文通过原文和一个正整数key加密形成，而key和密文又有一定关联。 现给出密文，求key值
已知密文s和key值关系如下 已知密文s是一串正整数s1,s2,s3……sn，A为s中所有元素的和，B为s中所有元素的积，key为B mod A 数据范围 si，A在(0,1e17]范围内,0< n < 100000 Input 第一行T表示数据组数 接下来每组第一行一个n，代表s的长度 接下来n行，每行一个正整数si Output 每组一行，key值
Sample Input 2 4 1 2 3 4 6 5 6 7 8 9 9 Sample Output 4 32 分析： 用long long储存数据，读入的时候得到 A ，用快速乘法两两相乘并取模得到 B 。
当时有点紧张，竟然连题意都没看懂，因为不会 FFT ，所以一看快速乘法就马上放弃，事后发现用最普通的快速乘法就能过/喷血 。 所以还是要学习一个 FFT 。
#include <iostream> #include <fstream> #include <functional> #include <cstdio> #include <sstream> #include <set> #include <bitset> #include <queue> #include <deque> #include <stack> #include <list> #include <vector> #include <map> #include <string> #include <cstring> #include <cmath> #include <cctype> #include <algorithm> using namespace std; typedef long long ll; typedef set<int> Set; typedef vector<int> Vec; typedef set<int>::iterator sIt; typedef vector<int>::iterator vIt; #define mem(s,t) (memset(s,t,sizeof(s))) #define D(v) cout<<#v<<" "<<v<<endl const int N = 100000+10; ll a[N]; ll quick_sig(ll a,ll b,ll p){ ll ans=0; a%=p; while(b){ if(b&1) ans=(ans+a)%p; b>>=1; a=(a<<1)%p; } return ans; } int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("o.txt","w",stdout); #endif ll T;scanf("%lld",&T); while(T--){ mem(a,0); ll n;scanf("%lld",&n); ll A=0,B=1; for(ll i=0;i<n;i++){ scanf("%lld",&a[i]); A+=a[i]; } ll ans=1; for(ll i=0;i<n;i++){ ans=quick_sig(ans,a[i],A); } printf("%lld\n",ans); } return 0; }快速乘法：
ll quick_sig(ll a,ll b,ll p){ ll ans=0; a%=p; while(b){ if(b%2==1) ans=(ans+a)%p; b/=2; a=(a+a)%p; } return ans; }用位运算符优化后：
ll quick_sig(ll a,ll b,ll p){ ll ans=0; a%=p; while(b){ if(b&1) ans=(ans+a)%p; b>>=1; a=(a<<1)%p; } return ans; }和快速幂的比较：
ll quick_mod(ll a,ll b,ll p){ ll ans=1; a%=p; while(b){ if(b&1) ans=ans*a%p; a=a*a%p; b>>=1; } return ans; }