先吐槽一波题目
然后再吐槽一波题目
然后再吐槽一波题目……
打住!(
下面是原题↓
原题
题目描述
公元21118年,世界变成一片废土,人们只能在绝望中残喘度过余生。
人类文明毁于一旦——原因是古老的书已无人能懂,大量知识被抛弃。
于是世界的智者们集合在一起,打算恢复知识的力量。
他们首先要振兴的,就是数学。
因为你刚刚拿了UOI(Universal Olympiad in Informatics)的AU,并且深知古
代数学那套理论,所以你作为这场大会的权威,解答大众的问题。
你要做的是,给出一个分数,求出它对 p=1e9+7 取模后的值。
输入输出格式
输入格式
第一行两个整数 a, b,为你所要求的分数 a/b 。
特别的,当你(出于各种原因)无法求解的时候,请输出“No Solution!”(不含
引号)。
输出格式
该分数对 p 取模后的值。
然后是改题√
题目描述
公元23333年,幻想乡变成一片废土,妖怪们只能在绝望中残喘度过余生。
幻想乡文明毁于一旦——原因是古老的书已无人能懂,大量知识被抛弃。
于是幻想乡的贤者们集合在一起,打算恢复知识的力量。
她们首先要振兴的,就是数学。
因为八云蓝刚刚拿了UOI(Universal Olympiad in Informatics)的AU,并且深知古
代数学那套理论,所以紫作为这场大会的权威,要求蓝解答大众的问题。
蓝还要帮紫准备东方华灯宴,所以把一个问题交给了你。
你要做的是,给出一个分数,求出它对 p=1e9+7 取模后的值。
输入输出格式
输入格式
第一行两个整数 a, b,为你所要求的分数 a/b 。
特别的,当你(出于各种原因)无法求解的时候,请输出“No Solution!”(不含
引号)。
输出格式
该分数对 p 取模后的值。
是不是无力吐槽了(
下边是给的标程(md这题太难了)
1 #include2 #include 3 #include 4 using namespace std; 5 typedef long long ll; 6 const ll p=1e9+7; 7 ll qpow(ll k,ll n){ 8 if(n==0)return 1; 9 if(n==1)return k%p;10 ll h=qpow(k,n/2)%p;11 if(n%2==0)return h%p*h%p;12 return h%p*h%p*k%p;13 }14 char a[2000002],b[2000002];15 ll c[2000001],d[2000001];16 ll g[2000001],h[2000001];17 ll e1=0,e2=0;18 int s1,s2;19 bool w=1;20 inline void init(){21 scanf("%s%s",a,b);22 if(a[0]=='-'){23 s1=strlen(a)-2;24 w=1-w;25 for(int i=0;i<=s1;i++){26 c[i]=a[i+1]-'0';27 }28 }else{29 s1=strlen(a)-1;30 for(int i=0;i<=s1;i++){31 c[i]=a[i]-'0';32 }33 }34 if(b[0]=='-'){35 s2=strlen(b)-2;36 w=1-w;37 for(int i=0;i<=s2;i++){38 d[i]=b[i+1]-'0';39 }40 }else{41 s2=strlen(b)-1;42 for(int i=0;i<=s2;i++){43 d[i]=b[i]-'0';44 }45 }46 return;47 }48 int main(){49 freopen("sleep.in","r",stdin);freopen("sleep.out","w",stdout);50 init();51 if(s2==0&&d[0]==0){52 printf("No Solution!\n");53 return 0;54 }55 if(s1==0&&c[0]==0){56 printf("0\n");57 return 0;58 }59 while(e1==0&&e2==0){60 int l1=-1,l2=-1;61 for(int i=0;i<=s1;i++){62 e1*=10;63 e1+=c[i];64 if(e1>=p){65 l1++;66 g[l1]=e1/p;67 e1%=p;68 }else if(l1!=-1){69 l1++;70 g[l1]=0;71 }72 }73 for(int i=0;i<=s2;i++){74 e2*=10;75 e2+=d[i];76 if(e2>=p){77 l2++;78 h[l2]=e2/p;79 e2%=p;80 }else if(l2!=-1){81 l2++;82 h[l2]=0;83 }84 }85 s1=l1;s2=l2;86 for(int i=0;i<=s1;i++)c[i]=g[i];87 for(int i=0;i<=s2;i++)d[i]=h[i];88 }89 if(e2==0&&e1!=0){90 printf("No Solution!\n");91 return 0;92 }93 ll ans=e1%p*qpow(e2,p-2)%p;94 if(!w&&ans)putchar('-');95 printf("%lld\n",ans);96 return 0;97 }
我相信你们一定看不完,因为我就没看完
(溜